algorithm - 交换两个相邻元素的最小数量

Question

如何找到交换数组的两个相邻元素的最小次数，以便没有元素等于它的索引。

IE，

array[i]!=i

示例 =>

I/P = [2,1,3]
O/P = 1 

标签： algorithmdata-structures

Answer 1

让我们称一个与其位置相等的元素为“错误”元素。

设 为错误元素的数量。目标是减少到零。

分析

如果允许重复值，这个问题会更复杂，但鉴于它们是不同的，我们可以观察到以下情况：

• 交换只有在减少 时才有用。如果不减少，则无法在未来的掉期中从该掉期中获益。
• 如果交换减少 2，它可能仍然不是最佳交换。例如，如果在 [1,2,3,4] 中我们首先交换 (2,3)，那么我们将需要再进行 2 次交换才能将其归零，而这可以仅使用两次交换来解决。在处理一组相邻的错误元素时，我们可以通过从第一对（或最后一对，...）开始来避免这种情况。

算法

• 如果数组只有一个元素并且它是错误的——即输入是 [1]——那么就没有可能的解决方案。
• 从左到右遍历数组。
• 当到达错误的元素时，如果有一个元素，则与下一个元素执行一次交换，否则与前一个元素交换。
• 返回进行的交换次数。

改进

我们实际上可以对此进行改进，只计算交换，而不是实际执行它们。在这种情况下，当我们计算当前元素与下一个元素的交换时，我们必须跳过下一个元素。这是为了避免当它也很糟糕时我们会为它计算另一个交换，因为当前的交换也会解决这个问题。另一方面，这个交换永远不会让下一个变坏，所以在计算这个交换时，我们可以安全地跳过检查下一个元素。

执行

这是一个 JavaScript 片段，它返回多个输入的结果：

function countSwaps(arr) {
    if (arr.length === 1 && arr[0] == 1) return Infinity; // No solution
    let count = 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] == i + 1) { // It is a bad element
            count++;
            // Skip the next element, because:
            // If it is bad, it is resolved by this swap
            // If it is good, it cannot turn bad by this swap
            i++;
        }
    }
    return count;
}

console.log(countSwaps([2,1,3]));  // 1
console.log(countSwaps([6,2,3,4,5,1]));  // 2
console.log(countSwaps([5,2,3,4,1]));  // 2
console.log(countSwaps([4,3,2,1,5]));  // 1
console.log(countSwaps([2]));  // 0
console.log(countSwaps([]));  // 0
console.log(countSwaps([1]));  // Infinity