找到时间复杂度优于 O(n) 的排序和移位数组的最小值

Question

我们有一个任务来搜索排序后向右移动的数组的最小元素。例如：[1, 5, 6, 19, 56, 101] 变为 [19, 56, 101, 1, 5, 6]。该方法应该使用分而治之算法来实现，并且它应该具有比 O(n) 更好的渐近时间复杂度。编辑：我忘了补充一点，数组中的元素是唯一的。

我已经实现了一种方法，想问一下这是否比 O(n) 更好，是否有改进我的方法的方法。

public class FindMinimum {

    public void findMinimum(int[] arr) {

        // the recursive method ends when the length of the array is smaller than 2

        if (arr.length < 2) {

            return;

        }

        int mid = arr.length / 2;

        /*

         * if the array length is greater or the same as two, check if the middle

         * element is smaller as the element before that. And print the middle element

         * if it's true.

         */

        if (arr.length >= 2) {

            if (arr[mid - 1] > arr[mid]) {

                System.out.println("Minimum: " + arr[mid]);

                return;

            }

        }

        /*

         * separate the array in two sub-arrays through the middle and start the method

         * with those two arrays again.

         */

        int[] leftArr = new int[mid];

        int[] rightArr = new int[arr.length - mid];

        for (int i = 0; i < mid; i++) {

            leftArr[i] = arr[i];

        }

        for (int i = mid; i < arr.length; i++) {

            rightArr[i - mid] = arr[i];

        }

        findMinimum(leftArr);

        findMinimum(rightArr);

    }

}

Answer 1

在 Java 中，您可以使用列表，因为您可以创建子列表。private Integer findMinimum(List<Integer> list) {&nbsp; &nbsp; if (list.size() < 2)&nbsp; &nbsp; &nbsp; &nbsp; return list.get(0);&nbsp; &nbsp; int mid = list.size() / 2;&nbsp; &nbsp; // create left and right list&nbsp; &nbsp; List<Integer> leftList = list.subList(0, mid);&nbsp; &nbsp; List<Integer> rightList = list.subList(mid, list.size());&nbsp; &nbsp; if (leftList.get(leftList.size() - 1) <= rightList.get(rightList.size() - 1))&nbsp; &nbsp; &nbsp; &nbsp; return findMin(leftList);&nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; return findMin(rightList);}当您使用 Java 创建子列表时，没有副本。所以创建一个新的子列表需要复杂度为 O(1)。所以该函数的复杂度为 O(logn)。

Answer 2

这是我的新解决方案，无需在任何地方复制数组。public class FindMinimum {&nbsp; &nbsp; public void findMinimum(int[] arr) {&nbsp; &nbsp; &nbsp; &nbsp; findMinimumSub(arr, 0, arr.length - 1, 2);&nbsp; &nbsp; }&nbsp; &nbsp; private void findMinimumSub(int[] arr, int start, int end, int size) {&nbsp; &nbsp; &nbsp; &nbsp; // the recursive method ends when the length of the array is smaller than 2&nbsp; &nbsp; &nbsp; &nbsp; if ((end - start) < 2) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (arr[end] > arr[start])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Minimum: " + arr[start]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Minimum: " + arr[end]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; int mid = arr.length / size;&nbsp; &nbsp; &nbsp; &nbsp; if (arr[start] > arr[end]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // right side&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start += mid;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; findMinimumSub(arr, start, end, size * 2);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // left side&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; findMinimumSub(arr, start, mid, size * 2);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}