我的代码有什么问题？- 如何知道数组是否可以通过只执行一次交换来排序？

Question

我相信我的代码工作正常，但它失败了一些测试用例。我看不出问题所在。

我得到了一个非空的整数数组。我应该只需要数组中的单个交换操作。换句话说，我需要检查数组是否可以通过仅执行一个交换操作来按非递减顺序排序。

例如：[1， 3， 5， 3， 7] 答案是：正确

总结： N 是 [1..100,000] 范围内的整数; 数组 A 的每个元素都是 [1..1,000,000,000] 范围内的整数。 复杂性： 预期的最坏情况时间复杂度为 O(N*log(N((;

function solution(A) {
var N = A.length;
var cnt = 0;
var B = A.slice();
B.sort();
for (var i = 0; i < N; i++) {
if(A[i] != B[i]) {
cnt++;
}
}
return  (cnt < 3);
}

它不起作用吗？

Answer 1

理解合并排序的最坏情况性能是O(N*lgN)。 因此，如果可以通过执行单个合并排序来回答您的问题，那么我们将有一个可接受的解决方案。 考虑按合并排序对数组进行排序，然后并排比较原始数组和排序数组：

original | sorted
7        | 7
3        | 5
5        | 3
3        | 3
1        | 1

现在只需遍历两个数组并计算不匹配的项目数。 如果您找到超过 2 个项目，则意味着涉及两个项目的单个交换无法纠正排序。

您可以将问题改写为询问数组的排序版本中有多少元素不合适。 如果只需要一次交换即可实现排序状态，则意味着只有两个项目不合适。