153 寻找旋转排序数组中的最小值

本文最后更新于：2021年3月31日 下午

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

示例 1：

1
2
输入：nums = [3,4,5,1,2]
输出：1

示例 2：

1
2
输入：nums = [4,5,6,7,0,1,2]
输出：0

示例 3：

1
2
输入：nums = [1]
输出：1

提示：

  • 1 <= nums.length <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数都是 唯一 的
  • nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转

Solution

  • 二分查找法
  • mid 与 r 比较，注意判断相等时的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// @lc code=start
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];

        int l = 0, r = n-1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] < nums[r]) {
                r = mid;
            } else if (nums[mid] > nums[r]) {
                l = mid + 1;
            } else {
                r = r + 1;
            }
        }
        return nums[l];
    }
};
// @lc code=end

扩展：数组先升序再降序（含重复元素） 用二分法求最大值

示例：一个数组先升序再降序，用最优时间复杂度，求最大值？例如[1,2,2,2,2,3,1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findMax(vector<int>& nums) {
    int n = nums.size();
    int l = 0, r = n-1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < nums[mid+1]) {
            l = mid + 1;
        } else if (nums[mid] > nums[mid+1]) {
            r = mid;
        } else {
            if (nums[l] > nums[r]) r--;
            else l++;
        }
    }
    return nums[l];
}
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！