LeetCode-153 Find Minimum in Rotated Sorted Array

爱被打了一巴掌 2021-11-16 23:48 207阅读 0赞

**题目描述**

Suppose an array sorted in ascending order 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.

**题目大意**

一个原本有序的数组被打乱一次，即从数组中的一个位置划分为两个子数组，将两个子数组位置互换（但子数组中的排列仍然保持），找到该乱序数组中的最小的数字。

**示例**

Input: [3,4,5,1,2] 
    Output: 1

Input: [4,5,6,7,0,1,2]
    Output: 0

**解题思路**

基于二分查找进行改进，在二分选择查询数字方向的时候需要判断mid是在什么位置（即是在交换后的较小的子数组中，还是在较大的子数组中）。

**复杂度分析**

时间复杂度：O(log(n))

空间复杂度：O(1)

**代码**

class Solution {
    public:
        int findMin(vector<int>& nums) {
            int n = nums.size();
            
            return solve(nums, 0, n - 1, n);
        }
        //二分查找
        int solve(vector<int>& nums, int low, int high, int n) {
            if(low == high)
                return nums[low];
            int mid = (low + high) / 2;
            // 如果两个边界指针相邻，说明最小值一定在其中，返回最小值即可;
            if(abs(low - high) == 1)
                return min(nums[low], nums[high]);
            //判断mid的具体位置
            if(mid > 0 && mid < n - 1)
                //mid如果恰好为最终答案，返回答案即可
                if(nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1])
                    return nums[mid];
                else {
                    //mid是在较大的子数组中
                    if(nums[mid] > nums[low] && nums[mid] > nums[high])
                        return solve(nums, mid + 1, high, n);
                    //low，mid，high在有序数组中，返回low即可
                    else if(nums[mid] > nums[low]) 
                        return nums[low];
                    //mid在较小的子数组中
                    else
                        return solve(nums, low, mid, n);
                }
            //mid在边界条件下，说明最小值一定在附近
            else if(mid > 0)
                return min(nums[mid], nums[mid - 1]);
            else
                return min(nums[mid], nums[mid + 1]);
        }
    };

转载于:https://www.cnblogs.com/heyn1/p/10937703.html