我试图解决这个面试问题。我的代码针对测试用例运行,但对于所有实际输入的测试用例均失败。我尽力找到错误,但未能成功。请在问题下方找到我的代码
鲍勃非常喜欢排序。他一直在思考排序数组的新方法,他的朋友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
。