交换两个相邻元素的最小数目

Question

如何找到数组的两个相邻元素的最小交换数，使任何元素都不等于它的索引。

即，

array[i]!=i

示例=>

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

Answer 1

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

让错误的元素数量。我们的目标是减少到零。

分析

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

只有当掉期减少时，

• 才会有用。如果掉期没有减少，那么在未来的掉期中就无法从这种掉期中获益。如果掉期减少2，
• 仍可能不是最佳互换。例如，如果在1,2,3,4中我们首先交换(2,3)，那么我们将需要2多个掉期才能使其变为零，而这可以用两个交换来解决。我们可以从第一对开始(或最后一对，.)来避免这一点。当处理一组相邻的错误元素时。

算法

如果数组只有一个元素，并且输入错误--即输入为1 --则不存在通过数组从左到右的possible.

• Iterate解决方案。当到达错误的元素时，
• 与下一个元素执行单个交换，否则与前一个元素进行交换。
• 返回所做的掉期数。

。

改进

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

实现

下面是一个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

​