最少调用 subArrayLeftShift 方法来排序数组（面试题）

Question

假设您有一个方法subArrayLeftShift(a,i)，当 n 是数组长度时，该方法将子数组 a[i,...,n-1] 左移。这意味着元素 a[i+1],...,a[n-1] 向左移动了一个位置，而原来的 a[i] 将成为最后一个。更正式地，这里是函数实现：public static void subArrayLeftShift(int[] a, int i){  if (a.length == 0) return;  int last = a.length - 1;  int insertToLast = a[i];  for (; i < last; i++){      a[i] = a[i + 1];  }  a[last] = insertToLast;}现在的问题是：实现一个接收未排序数组的函数，并返回对数组排序的最少调用次数subArrayLeftShift。在采访中，我找不到办法做到这一点。我成功地为我为直觉而编写的每个示例找到了最少的调用次数，但找不到概括它的方法。你知道如何解决吗？

Answer 1

我提出以下算法来解决这个问题：

• 找出数组中未排序的最小数字（数组右侧的数字较小）。将此数字设为x。

• 计算数组中有多少数字大于先前找到的数字x。将此数字设为y。

由于每次调用函数时，未排序的数字都会在最后一个位置结束，因此最佳策略是按递增顺序为每个未排序的数字调用函数。使用之前找到的内容，我们从x开始。我们继续下一个大于 x 的未排序数字，因为这样，它将在x的右侧结束，因此它将被排序。以同样的方式继续。多少？我们有多少比x大的数？嗯，就是y。所以总的来说，对该函数的调用次数是1 + y。

Answer 2

public static int minimumCalls(int[] a) {

    int minCalls = 0;

    for (int i = 0; i < a.length - 1; i++) {

        for (int j = i+1; j < a.length; j++) {

            if (a[i] > a[j]) {

                minCalls++;

                break;

            }

        }

    }

    return minCalls;

}

我的想法背后的想法是，只要 SubArray 中存在任何小于 current 的值，就必须调用该方法一次i。subArrayShiftLeft我觉得这个方法的名字是为了让你远离并把你的注意力从容易地想这个问题上拉开。

如果数组中有任何小于当前值的值，只需调用该方法。

将此视为将单个较大的值移动到数组的末尾比尝试将较小的值向左移动要容易得多。