Leetcode 题目解析之 Find Minimum in Rotated Sorted Array

原创

ruochen

发布于 2022-01-08 14:53:58

1.4K0

发布于 2022-01-08 14:53:58

文章被收录于专栏：若尘的技术专栏若尘的技术专栏

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

数列基本有序，则使用二分查找。假设数列是n，s是起始下标，e是最后下标，m是中间元素下标。分为三种情况：

ns < ne

nm > ns > ne

nm < ne < ns

情况1：ns < ne

0 1 2 4 5 6 7

这种情况，直接返回ns。因为数列是有序的，或者只是旋转过一次。如果ns < ne，则表明没有旋转。最小元素是ns。

情况2：nm > ns > ne

4 5 6 7 0 1 2

    public int findMin(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.min(nums[0], nums[1]);
        }
        int s = 0, e = nums.length - 1;
        int m = (s + e) / 2;
        if (nums[s] < nums[e]) {
            return nums[s];
        }
        if (nums[m] > nums[s]) {
            return findMin(Arrays.copyOfRange(nums, m + 1, e + 1));
        }
        return findMin(Arrays.copyOfRange(nums, s, m + 1));
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

element