当前位置：首页 > news >正文

旋转数组的最小数字 -- java

news 来源：原创 2024/4/29 13:44:13

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个 非递减 排序的数组的一个旋转，输出旋转数组的最小元素。例如数组 {3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转，该数组的最小值为 1。

NOTE：若数组大小为 0，请返回 0。

解题思路

如果遇到从排序的数组中查找数字需要尝试二分查找法。

我们利用两个指针分别指向数组的第一个元素和最后一个元素，我们可以先找到数组中间的元素，如果该中间元素大于或等于第一个元素，则位于前面的非递减子数组，此时我们就可以把第一个指针指向该中间元素，这样就可以缩小寻找的范围，移动以后，第一个指针依然指向前面的非递减数组；

否则属于后面的非递减子数组，此时我们就可以把第二个指针指向该中间元素，移动以后，第二个指针依然指向后面的非递减数组。然后循环下去，最终第一个指针将指向前面子数组的最后一个元素，而第二个指针将会指向后面子数组的第一个元素，而第二个指针指向的刚好是最小的元素。循环结束。

PS：我们要注意在参考解题中main函数里的特例，如果两个指针以及中间的元素指向的三个数字相等，就只能顺序查找。

代码

public class Min {
    /**
     * 获取旋转数组的最小数字
     * @param numbers 旋转数组
     * @return 最小数字
     * @throws Exception
     */
    public static int min(int[] numbers) throws Exception {
        if (numbers == null || numbers.length == 0) {
            throw new Exception("Invalid parameters");
        }
        int length = numbers.length;

        // index1永远为前一个非递减的数组指针
        int index1 = 0;
        // index2永远为后一个非递减的数组指针
        int index2 = length-1;
        // middle永远指向中间的值，当旋转数据就是原数组时，返回第1个数字
        int indexMid = index1;

        while (numbers[index1] >= numbers[index2]) {
            if (index2 - index1 == 1) {
                indexMid = index2;
                break;
            }

            indexMid = (index1 + index2) / 2;

            // 如果下标i, j, middle 指向的三个数字相等，就只能顺序查找
            if (numbers[index1] == numbers[index2] && numbers[index1] == numbers[indexMid]) {
                return minInOrder(numbers, index1, index2);
            }

            if (numbers[indexMid] >= numbers[index1]) {
                index1 = indexMid;
            } else if (numbers[indexMid] <= numbers[index2]) {
                index2 = indexMid;
            }
        }

        return numbers[indexMid];
    }

    /**
     * 顺序找出旋转数组中最小的值
     * 因为有序，只要找到第一个递减的值就可以返回了
     * @param numbers
     * @param index1
     * @param index2
     * @return
     */
    public static int minInOrder(int[] numbers, int index1, int index2) {
        int result = numbers[index1];
        for (int i = index1+1; i <= index2; i++) {
            if (result > numbers[i]) {
                result = numbers[i];
            }
        }
        return result;
    }

    // 测试
    public static void main(String[] args) throws Exception {
        int[] numbers = {3,4,5,1,2};
        System.out.println(min(numbers));
    }
}