最大正整数

记录自己一道没有做出来的面试题。

数组中存储了一堆小于10的非负整数，整个数组从左到右代表一个正整数（如数组[0, 1, 3, 2]代表正整数132）。现给出一个正整数K，要求经过K次数组相邻位置元素交换（必须完成K次交换），使得这个数组代表的数字最大。
例如,
int array[] = {0, 1, 3, 2}, K = 1，则经过1次交换后，数组所能代表的最大值为1032；
int array[] = {0, 1, 3, 2}, K = 2，则经过2次交换后，数组所能代表的最大值为3012。

输入描述:

首先，输入一个正整数T，表示接收T组测试用例；

此后，输入T组测试用例，其中每组测试用例包含如下内容：

输入1：一个正整数K，表示在当前测试用例中，可以对数组进行K次相邻元素间的位置交换；

输入2：一个正整数N，表示当前用例包含数组的长度；

输入3：N个数组元素，所有元素都是小于10的非负整数；

输出描述:

输出共N行，对应于N个用例的输出：

每行输出为一个数组，数组元素之间用一个空格隔开，要求每行输出前后均无多余空格。

思路

k次交换，如果k无穷大（其实大于n*(n-1) / 2 就会已经排好序了），最后数组应该是一个降序的排序。

k次交换，i从0开始，就是可以最远将nums[i+k]的元素交换到nums[i], 所以就是首先将0-k之间最大的元素交换到开头
，如果还有剩余交换次数就继续交换，直到交换次数用完。时间复杂度为(n^2)

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1000005;
int a[N];
int k, n;

int *findMax(int a[], int k) {
    if (k > n * (n - 1) / 2) {
        sort(a, a+n);
        return a;
    }
    if (k <= 0) return a;
    for (int i = 0; i < n; i++) {
        int num = a[i];
        int idx = i;
        for (int j = i; j < n && j < i + k + 1; j++) {
            // 记录到k之间最大的元素，以及下标
            if (a[j] > num) {
                num = a[j];
                idx = j;
            }
        }
        for (int t = idx; t > i; t--) {
            if (k > 0) {
                int temp = a[t];
                a[t] = a[t-1];
                a[t-1] = temp;
                k--;
            } else {
                return a;
            }
        }
    }
    return a;
}


int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> k >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        findMax(a, k);
        for (int i = 0; i < n; i++) {
            cout << a[i] << " ";
        }
        puts("");
    }
    return 0;
}