找到时间复杂度优于 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) {

    if (list.size() < 2)

        return list.get(0);

    int mid = list.size() / 2;

    // create left and right list

    List<Integer> leftList = list.subList(0, mid);

    List<Integer> rightList = list.subList(mid, list.size());

    if (leftList.get(leftList.size() - 1) <= rightList.get(rightList.size() - 1))

        return findMin(leftList);

    else

        return findMin(rightList);

}

当您使用 Java 创建子列表时，没有副本。所以创建一个新的子列表需要复杂度为 O(1)。所以该函数的复杂度为 O(logn)。

Answer 2

这是我的新解决方案，无需在任何地方复制数组。

public class FindMinimum {

    public void findMinimum(int[] arr) {

        findMinimumSub(arr, 0, arr.length - 1, 2);

    }

    private void findMinimumSub(int[] arr, int start, int end, int size) {

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

        if ((end - start) < 2) {

            if (arr[end] > arr[start])

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

            else

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

            return;

        }

        int mid = arr.length / size;

        if (arr[start] > arr[end]) {

            // right side

            start += mid;

            findMinimumSub(arr, start, end, size * 2);

        }

        else {

            // left side

            findMinimumSub(arr, start, mid, size * 2);

        }

    }

}