我试图解决这个面试问题。我的代码针对测试用例运行,但对于所有实际输入的测试用例均失败。我尽力找到错误,但未能成功。请在问题下方找到我的代码


  鲍勃非常喜欢排序。他一直在思考排序数组的新方法,他的朋友Ram给他带来了艰巨的任务。他给鲍勃一个数组和一个整数K。面临的挑战是在最多K次交换之后产生字典最小数组。只能交换连续的元素对。帮助Bob在最多进行K交换后返回字典最小数组。
  
  输入:第一行包含一个整数T,即测试用例的数量。 T测试用例如下。每个测试用例有2行。第一行包含N(number of elements in array)K(number of swaps)。第二行包含数组的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



{1,5,3}在字典上小于{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;

}

最佳答案

这是两个失败的测试用例。

2

2 2
2 1

5 3
3 2 1 5 4


在第一个中,您的代码不进行任何交换,因为K> =N。在第二个中,您的代码在应将其第三次交换用于3和2时交换5和4。

编辑:新版本仍然过于贪婪。正确的输出

1

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




1 2 3 4 5 10 9 8 7 6


07-24 09:46
查看更多