VIRTUALS

the virtual labs for the virtuals

0%

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

Posted on Edited on In , , ,

摘要：
二分查找经典应用。

题目

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

示例 1：

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

示例 2：

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

二分查找

本题与 寻找旋转排序数组中的最小值 II 完全一致。

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
28
29
30
// 执行用时: 4 ms
// 内存消耗: 11.8 MB
class Solution {
public:
    int len;
    int findMin(vector<int>& nums) {
        len = nums.size();

        int lo = 0, hi = len - 1;

        // 特判非递减情况（折叠点不在原数组下标范围内）
        if (nums[hi] > nums[lo]) return nums[lo];

        // 特判折叠点在重复数字中的情况（折叠后数组首尾相同）
        for (; lo < hi && nums[hi] == nums[0]; hi--); 

        // 此时存在两种情况，一是右半边还有数字，二是右半边无数字
        // 如果是右半边有数字，那么右半边递增，全部数字小于num[0];
        // 如果右半边没有数字，也就是说hi到了左半边，直接返回nums[0];
        if (nums[hi] > nums[0]) return nums[lo];

        // 常规情况，和153题解法一致
        for (; lo < hi;) {
            int mid = lo + hi >> 1;
            if (nums[mid] >= nums[0]) lo = mid + 1;
            else hi = mid;
        }
        return nums[lo];
    }
};
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
// 执行用时: 0 ms
// 内存消耗: 38.3 MB
class Solution {
    int len;
    public int findMin(int[] nums) {
        len = nums.length;

        int lo = 0;
        int hi = len - 1;
        
        if (nums[hi] > nums[lo]) return nums[0];

        for (; lo < hi && nums[lo] == nums[hi]; hi--);

        if (nums[hi] > nums[lo]) return nums[0];

        for (; lo < hi;) {
            int mid = lo + hi >> 1;
            if (nums[mid] >= nums[0]) lo = mid + 1;
            else hi = mid;
        } 

        return nums[lo];
    }
}

暴搜

暴力Loop一把梭，复杂度为 $O(N)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 执行用时: 4 ms
// 内存消耗: 11.8 MB
class Solution {
public:
    int len;
    int minArray(vector<int>& numbers) {
        len = numbers.size();

        for (int i = 1; i < len; i++) {
            if (numbers[i] < numbers[i - 1]) return numbers[i];
        }

        return numbers[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 执行用时: 0 ms
// 内存消耗: 38.3 MB
class Solution {
    int len;
    public int minArray(int[] numbers) {
        len = numbers.length;

        for (int i = 1; i < len; i++) {
            if (numbers[i] < numbers[i - 1]) return numbers[i];
        }

        return numbers[0];
    }
}

原题链接： 剑指Offer 11. 旋转数组的最小数字