Keshawn_lu's Blog

Leetcode 剑指 Offer 11. 旋转数组的最小数字

数组 二分查找
字数统计: 394阅读时长: 1 min
2020/07/22 Share

题目简介：

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

示例 1：

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

示例 2：

1
2
输入：[2,2,2,0,1]
输出：0

思路：

摸鱼做法：直接sort，返回数组最小值即可。

二分做法：设最小值在数组的下标为min，将每次的numbers[mid]与numbers[right]比较，存在三种情况：

  1. numbers[mid] < numbers[right]，此时mid位于[min, right)，所以将right = mid。

  2. numbers[mid] > numbers[right]，此时mid位于[left, min)，所以将left = mid + 1。

  3. numbers[mid] = numbers[right]，此时无法判别mid位于最小值的左侧还是右侧，就像下面这个例子一样，numbers[mid] = numbers[right] = 1。所以将right--，缩小范围。

    1
    [1, 1, 1, 0, 1, 1, 1]

最后返回numbers[left]即可。

tip:

  • 用numbers[right]作比较的原因通过与它的比较，能得出numbers[mid]在最小值的左侧还是右侧，而numbers[left]则不行。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minArray(vector<int>& numbers) {

        int left = 0;
        int right = numbers.size() - 1;

        while(left <= right){

            int mid = (right - left) / 2 + left;

            //mid在最小值左侧
            if(numbers[mid] > numbers[right])
                left = mid + 1;

            //mid在最小值右侧
            else if(numbers[mid] < numbers[right])
                right = mid;

            //无法判断mid在左侧还是右侧
            else
                right--;
        }

        return numbers[left];
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网