寻找最小字典式数组

Question

我试图解决这个面试问题。我的代码针对测试用例运行，但对于所有实际输入测试用例都失败。我努力寻找错误，但无法做到。请在问题下方找到我的代码

鲍勃非常喜欢分类。他总是在想新的方法来对数组进行排序。他的朋友拉姆给了他一项艰巨的任务。他给了Bob一个数组和一个整数K。挑战是在最多K-swap之后生成字典序最小数组。只能交换连续的元素对。帮助Bob在最多K-swap之后返回字典序最小数组。

输入：第一行包含一个整数T，即测试用例的数量。T测试用例紧随其后。每个测试用例有2行。第一行包含N（数组中元素的数量）和K（交换的数量）。第二行包含n数组的整数。

输出：打印字典最小数组。

约束条件:

1 <= T <= l0 

1 <= N,K <= 1000 

1 <= A[i] <= 1000000 

示例输入（纯文本链接）

2 

3 2 

5 3 1 

5 3 

8 9 11 2 1 

样本输出（纯文本链接）

1 5 3 

2 8 9 11 1 

说明

交换1后：

5 1 3 

交换2后：

1 5 3 

< code>{1，5，3}在字典上比< code>{5，1，3}小

示例 2：

交换1: 8 9 2 11 1

交换2：8 2 9 11 1

交换 3： 2 8 9 11 1

  #include <iostream>
  using namespace std;

  void trySwap(int a[], int start, int end, int *rem)
  {
//cout << start << "  " << end << "  " << *rem << endl;
  while (*rem != 0 && end > start)
  {
    if (a[end - 1] > a[end])
    {
        swap(a[end - 1], a[end]);
        (*rem)--;
        end--;
    }
    else end--;
}
}

void getMinimalLexicographicArray(int a[], int size, int k)
{
int start , rem = k, window = k;

for (start = 0; start < size; start++)
{
    window = rem;
    if (rem == 0)
        return;
    else
    {
        //cout << start << " " << rem << endl;
        int end = start + window;
        if (end >= size)
        {
            end = size - 1;
        }
        trySwap(a, start, end, &rem);
    }
}
}

int main()
{
int T, N, K;
int a[1000];
int i, j;

cin >> T;
for (i = 0; i < T; i++)
{
    cin >> N;
    cin >> K;

    for (j = 0; j < N; j++)
    {
        cin >> a[j];
    }

    getMinimalLexicographicArray(a, N, K);

    for (j = 0; j < N; j++)
        cout << a[j] << " ";
    cout << endl;

}

return 0;

}

Answer 1

下面是两个失败的测试用例。

2

2 2
2 1

5 3
3 2 1 5 4

首先，您的代码不进行交换，因为 K

编辑:新版本还是太贪心了。的正确输出

1

10 10
5 4 3 2 1 10 9 8 7 6

是

1 2 3 4 5 10 9 8 7 6

.

Answer 2

Python解决方案可以很容易地翻译成C:

def findMinArray(arr, k):
  i = 0
  n = len(arr)

  while k > 0 and i < n:
    min_idx = i

    hi = min(n, i + k + 1)

    for j in range(i, hi):
      if arr[j] < arr[min_idx]:
        min_idx = j

    for j in range(min_idx, i, -1):
      arr[j - 1], arr[j] = arr[j], arr[j - 1]

    k -= min_idx - i
    i += 1

  return arr