java - 如何快速恢复随机交换 2 个元素的递增数组？

Question

如果我有一个数组 A = [1, 2, 3, 4, 5, 6, 7]，A 是一个递增的数组，没有重复的元素.如果我交换两个元素，比如说 4 和 7。我得到数组 B = [1, 2, 3, 7, 5, 6, 4]。

给定数组B，恢复A的快速方法是什么？

目前，天真的方法是使用 Collections sort 方法对数组进行排序并比较以获得两个不同的索引，这花费 O(n) 空间以及 O(n) 时间。

为了让问题更清楚，这里给你输入 B 并且应该输出 B

Answer 1

只需从左到右搜索交换的元素，并在找到时交换它们。

// Let' assume the array is stored in a variable 'arr'

private void restoreArray() {
    swap(getLeftSwapIndex(), getRightSwapIndex());
}

private void swap(int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

private void getLeftSwapIndex() {
    for (int i=0 ; i<arr.length-1 ; i++) {
        if (arr[i] > arr[i+1]) return i;
    }
    return 0; // does not happen
}

private void getRightSwapIndex() {
    for (int i=arr.length-1 ; i>0 ; i--) {
        if (arr[i] < arr[i-1]) return i;
    }
    return 0; // does not happen
}