寻找最小的辞典阵列

我试着解决这个面试问题。我的代码针对测试用例运行，但对于所有实际输入测试用例都失败。我尽力找到错误，但无法做到这一点。请在问题的下方找到我的代码寻找最小的辞典阵列

Bob非常喜欢排序。他总是在思考排序阵列的新方法。他的朋友Ram给了他一项具有挑战性的任务。他给了Bob一个数组和一个整数K.挑战是在至多K次交换之后产生词典最小阵列。只有连续的元素对可以交换。帮助鲍勃在最多K次交换后返回可能的字典式最小阵列。

输入：第一行包含整数T即测试用例的数量。 T测试用例如下。每个测试用例都有2行。第一行包含N(number of elements in array)和K(number of swaps)。第二行包含数组的整数。

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

限制条件：
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; 

}

来源

2014-08-28 user2221214

你能链接问题的来源，以便我们可以验证它不是来自跑步比赛吗？ – 2014-08-28 01:45:07

http://www.careercup.com/page?pid=directi-interview-questions – user2221214 2014-08-28 01:51:13

以下是原文：http://www.hackerearth.com/problem/algorithm/swap-it-2/。这是一个实践问题。 – 2014-08-28 01:56:22

这里有两个失败的测试用例。

在第一，您的代码是没有互换，因为K> = N。在第二，您的代码互换5和4时，它应该把它的第三交换3和2

EDIT ：新版本仍然过于贪婪。对于

1 

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

正确的输出是

1 2 3 4 5 10 9 8 7 6

。

来源

2014-08-28 02:10:17

@ user2221214仍然是越野车。 – 2014-08-28 04:29:51

只能交换连续的元素对。预期的答案必须是1 5 4 3 2 10 9 8 7 6 – gout 2017-06-09 03:46:25

寻找最小的辞典阵列

回答

相关问题