arrays - 查找对给定数组进行排序所需的先删除后追加操作数

Question

这是一道面试题。Aswap表示从数组中删除任何元素并将其附加到同一数组的后面。给定一个整数数组，找出对swaps数组进行排序所需的最小数目。

有比 更好的解决方案O(n^2)吗？

例如：

输入数组：[3124]。

数量swaps：2（[3124] -> [1243] -> [1234]）。

Answer 1

问题归结为找到作为输入数组中的子序列出现的排序数组的最长前缀。这决定了不需要排序的元素。剩下的元素需要从小到大一一删除，在后面追加。

在您的示例中[3, 1, 2, 4]，已排序的子序列是[1, 2]。最佳解决方案是删除剩余的两个元素，3和4，并将它们附加在后面。因此，最佳解决方案是两次“交换”。

可以O(n logn)使用O(n)额外的内存及时找到子序列。以下伪代码将执行此操作（代码也恰好是有效的 Python）：

l = [1, 2, 4, 3, 99, 98, 7]
s = sorted(l)
si = 0
for item in l:
  if item == s[si]:
    si += 1
print len(l) - si

如果，如您的示例所示，数组包含从1到的整数排列n，则可以O(n)使用O(1)内存及时解决问题：

l = [1, 2, 3, 5, 4, 6]
s = 1
for item in l:
  if item == s:
    s += 1
print len(l) - s + 1

更一般地说，只要我们先验地知道输出数组，就可以使用第二种方法，因此不需要通过排序找到它。

Answer 2

O(nlogn)即使我们不假设连续值数组，这也可能有效。
如果我们这样做 - 它可以在O(n). 一种方法是使用O(n)空间和O(nlogn)时间。
给定数组A将它（）排序O(nlogn)为第二个数组B。
现在...（数组从 1 开始索引）

swaps = 0
b = 1
for a = 1 to len(A)
  if A[a] == B[b]
    b = b + 1
  else
    swaps = swaps + 1

Answer 3

观察：如果一个元素被交换到后面，它之前的位置无关紧要。没有元素需要多次交换。

观察：最后的交换（如果有的话）必须移动最大的元素。

观察：在交换之前，数组（不包括最后一个元素）必须排序（通过前交换，或最初）

排序算法，假设值是连续的：找到从 1 开始的连续（按值）元素的最长排序子序列：

3 1 5 2 4

依次交换所有更高的元素：

1 5 2 4 3

1 5 2 3 4

1 2 3 4 5

要找到 O(n) 中的交换次数，请找到从 1 开始的连续元素的最长排序子序列的长度：

• 预期 = 1
• 对于序列中的每个元素
  • 如果元素 == 预期
    • 预期 += 1
• 返回预期-1

那么交换的数量 = 输入的长度 - 它的最长排序子序列。

如果输入不是 1..n 的排列，则另一种解决方案（ O(n^2) ）：

• 掉期 = 0
• 环形
  • 找到最大元素的第一个实例并检测数组是否已排序
  • 如果数组已排序，则返回交换。
  • 否则从数组中删除找到的元素并增加交换。

另一个解决方案（ O(n log n) ），假设独特的元素：

• 将每个元素包装在 {oldPos, newPos, value}
• 制作数组的浅拷贝
• 按值对数组进行排序
• 存储每个元素的新位置
• 对（未排序的）副本中的 newPos' 运行排列算法

如果您不想复制输入数组，请在最后一步之前按 oldPos 排序。

Answer 4

这可以在 O(n log n) 中完成。

首先找到数组中的最小元素。现在，找到出现在该元素之前的最大元素。打电话给这个max_left。swap()您必须在数组的 min 元素之前调用所有元素。

现在，找到最小元素右侧的最长递增子序列，以及应该跳过值大于 max_left 的元素的约束。所需的交换次数是size(array) - size(LIS)。

例如考虑数组，

7 8 9 1 2 5 11 18

数组中的最小元素是 1。所以我们在最小元素之前找到最大值。

7 8 9 | 1 2 5 11 18

max_left = 9

现在，找到元素 < 9 LIS = 1,2,5 的 min 右侧的 LIS

掉期数 = 8 - 3 = 5

在 max element 为 null 的情况下，即 min 是第一个元素，找到数组的 LIS 并且所需的答案是 size(array)-size(LIS)

例如

2 5 4 3

max_left 为空。LIS 是2 3

交换数 = 大小（数组） - 大小（LIS） = 4 - 2 = 2

Answer 5

这是python中用于最小交换次数的代码，

def find_cycles(array):
   cycles = []
   remaining = set(array)
   while remaining:
      j = i = remaining.pop()
      cycle = [i]
      while True:
         j = array[j]
         if j == i:
             break
         array.append(j)
         remaining.remove(j)
      cycles.append(cycle)
   return cycles

def minimum_swaps(seq):
    return sum(len(cycle) - 1 for cycle in find_cycles(seq))

Answer 6

O(1) 空间和 O(N) (~ 2*N) 解决方案假设 min 元素为 1，并且数组包含从 1 到 N-1 的所有数字，没有任何重复值。其中 N 是数组长度。

int minimumSwaps(int[] a) {
    int swaps = 0;
    int i = 0;
    while(i < a.length) {
        int position = a[i] - 1;
        if(position != i) {
            int temp = a[position];
            a[position] = a[i];
            a[i] = temp;
            swaps++;
        } else {
            i++;
        }
    }
    return swaps;
}

Answer 7

int numSwaps(int arr[], int length) {
bool sorted = false; 
int swaps = 0;
while(!sorted) {
    int inversions = 0;
    int t1pos,t2pos,t3pos,t4pos = 0;
    for (int i =  1;i < length; ++i)
    {
        if(arr[i] < arr[i-1]){
            if(inversions){
                tie(t3pos,t4pos) = make_tuple(i-1, i);
            }
            else tie(t1pos, t2pos) = make_tuple(i-1, i);
            inversions++;
        }
        if(inversions == 2)
            break;
    }
    if(!inversions){
        sorted = true;
    }
    else if(inversions == 1) {
        swaps++; 
        int temp = arr[t2pos];
        arr[t2pos] = arr[t1pos];
        arr[t1pos] = temp;
    }
    else{
        swaps++;
        if(arr[t4pos] < arr[t2pos]){
            int temp = arr[t1pos];
            arr[t1pos] = arr[t4pos];
            arr[t4pos] = temp;
        }
        else{
            int temp = arr[t2pos];
            arr[t2pos] = arr[t1pos];
            arr[t1pos] = temp;
        }
    }
}
return swaps;
}

此代码返回对数组进行就地排序所需的最小交换次数。

例如，A[] = [7,3,4,1] 通过交换 1 和 7，我们得到 [1,3,4,7]。类似地 B[] = [1,2,6,4,8,7,9]。我们首先将 6 与 4 交换，因此，B[] -> [1,2,4,6,8,7,9]。然后是 7 和 8。所以 -> [1,2,4,6,7,8,9]

该算法以 O(索引 i < 索引 i-1 处的值的对数) ~ O(N) 运行。

Answer 8

编写一个非常简单的 JavaScript 程序来对数组进行排序并找到交换次数：

  function findSwaps(){

    let arr = [4, 3, 1, 2];
    let swap = 0
    var n = arr.length
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                arr[i] = arr[i] + arr[j];
                arr[j] = arr[i] - arr[j];
                arr[i] = arr[i] - arr[j]
                swap = swap + 1
            }
        }
    }
    console.log(arr);
    console.log(swap)
  }

Answer 9

for(int count = 1; count<=length; count++)
{
    tempSwap=0; //it will count swaps per iteration
    for(int i=0; i<length-1; i++)
        if(a[i]>a[i+1])
        {
           swap(a[i],a[i+1]);
           tempSwap++;
        }
    if(tempSwap!=0) //check if array is already sorted!
        swap += tempSwap;
    else
        break;
}
System.out.println(swaps);

Answer 10

这是适用于所有输入的 O(n) 解决方案：

static int minimumSwaps(int[] arr) {
        int swap=0;
        boolean visited[]=new boolean[arr.length];

        for(int i=0;i<arr.length;i++){
            int j=i,cycle=0;

            while(!visited[j]){
                visited[j]=true;
                j=arr[j]-1;
                cycle++;
            }

            if(cycle!=0)
                swap+=cycle-1;
        }
        return swap;
    }
}

Answer 11

def minimumSwaps(arr):
    swaps = 0
    '''
    first sort the given array to determine the correct indexes 
    of its elements
    '''
    temp = sorted(arr)

    # compare unsorted array with the sorted one
    for i in range(len(arr)):
        '''
        if ith element in the given array is not at the correct index
        then swap it with the correct index, since we know the correct
        index because of sorting. 
        '''
        if arr[i] != temp[i]: 
          swaps += 1
          a = arr[i]
          arr[arr.index(temp[i])] = a
          arr[i] = temp[i]    
    return swaps

Answer 12

如果您注意到在以下情况下需要删除并附加数组中的元素，我认为这个问题可以在 O(N) 中解决：

• 右侧有一个较小的元素或...
• 他的左边有一个较小的元素需要删除和附加。

然后它只是识别需要删除和附加的元素。这是代码：

static int minMoves(int arr[], int n) {
    if (arr.length == 0) return 0;

    boolean[] willBeMoved = new boolean[n]; // keep track of elements to be removed and appended
    int min = arr[n - 1]; // keep track of the minimum

    for (int i = n - 1; i >= 0; i--) { // traverse the array from the right
        if (arr[i] < min) min = arr[i]; // found a new min
        else if (arr[i] > min) { // arr[i] has a smaller element to the right, so it will need to be moved at some point
            willBeMoved[i] = true;
        }
    }

    int minToBeMoved = -1; // keep track of the minimum element to be removed and appended
    int result = 0; // the answer

    for (int i = 0; i < n; i++) { // traverse the array from the left
        if (minToBeMoved == -1 && !willBeMoved[i]) continue; // find the first element to be moved
        if (minToBeMoved == -1) minToBeMoved = i;

        if (arr[i] > arr[minToBeMoved]) { // because a smaller value will be moved to the end, arr[i] will also have to be moved at some point
            willBeMoved[i] = true;
        } else if (arr[i] < arr[minToBeMoved] && willBeMoved[i]) { // keep track of the min value to be moved
            minToBeMoved = i;
        }

        if (willBeMoved[i]) result++; // increment
    }

    return result;
}

它使用 O(N) 空间。

Answer 13

@all ，@Itay karo 和 @NPE 提供的公认解决方案是完全错误的，因为它不考虑交换元素的未来顺序......

它对于许多测试用例都失败了，例如：

3 1 2 5 4

正确输出：4

但他们的代码输出为3 ...

解释： 3 1 2 5 4--->1 2 5 4 3--->1 2 4 3 5--->1 2 3 5 4--->1 2 3 4 5

PS：由于声誉低，我无法在那里发表评论

Answer 14

听听我在 c# 中的解决方案，以解决缩短数组所需的最小交换次数当时我们只能交换 2 个元素（在任何索引位置）。

public class MinimumSwaps2
{
    public static void minimumSwapsMain(int[] arr)
    {

        Dictionary<int, int> dic = new Dictionary<int, int>();
        Dictionary<int, int> reverseDIc = new Dictionary<int, int>();
        int temp = 0;
        int indx = 0;
  //find the maximum number from the array
        int maxno = FindMaxNo(arr);

        if (maxno == arr.Length)
        {
            for (int i = 1; i <= arr.Length; i++)
            {
                dic[i] = arr[indx];
                reverseDIc.Add(arr[indx], i);
                indx++;
            }
        }
        else
        {
            for (int i = 1; i <= arr.Length; i++)
            {
                if (arr.Contains(i))
                {
                    dic[i] = arr[indx];
                    reverseDIc.Add(arr[indx], i);
                    indx++;
                }

            }
        }

        int counter = FindMinSwaps(dic, reverseDIc, maxno);


    }
    static int FindMaxNo(int[] arr)
    {
        int maxNO = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            if (maxNO < arr[i])
            {
                maxNO = arr[i];
            }
        }
        return maxNO;
    }
    static int FindMinSwaps(Dictionary<int, int> dic, Dictionary<int, int> reverseDIc, int maxno)
    {
        int counter = 0;
        int temp = 0;
        for (int i = 1; i <= maxno; i++)
        {
            if (dic.ContainsKey(i))
            {
                if (dic[i] != i)
                {
                    counter++;
                    var myKey1 = reverseDIc[i];
                    temp = dic[i];
                    dic[i] = dic[myKey1];
                    dic[myKey1] = temp;

                    reverseDIc[temp] = reverseDIc[i];
                    reverseDIc[i] = i;
                }
            }
        }
        return counter;
    }
}

Answer 15

int temp = 0, swaps = 0;
        for (int i = 0; i < arr.length;) {
            if (arr[i] != i + 1){ 
            //  System.out.println("Swapping --"+arr[arr[i] - 1] +"  AND -- "+arr[i]);
                temp = arr[arr[i] - 1];
                arr[arr[i] - 1] = arr[i];
                arr[i] = temp;
                ++swaps;
            } else
                ++i;
                //  System.out.println("value at position -- "+ i +" is set to -- "+ arr[i]);
        }
        return swaps;

这是我找到的最优化的答案。就是这么简单。您可能会通过循环一看就明白。感谢黑客级别的达里尔。