排序数组对subArrayLeftShift方法的最小调用(面试问题)

Question

假设您有一个方法subArrayLeftShift(a,i)，当n是数组长度时，它向左移动子数组ai，.，n-1。这意味着元素ai+1，.，an-1正在向左移动一个位置，而原来的ai将成为最后一个。

更正式地说，以下是功能实现：

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中存在任何小于当前i的值，就必须调用该方法一次。方法subArrayShiftLeft的名字，我觉得，是设计用来抛开你，把你的注意力从这个容易的想法中移开。

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

当将单个更大的值移到数组的末尾时，要比尝试将较小的值移到左要容易得多。