仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

旋转数组

发表于 更新于 分类于 ，
本文字数： 3k 阅读时长 ≈ 3 分钟

【道德经·第二十九章】将欲取天下而为之，吾见其不得已。天下神器，不可为也，不可执也。为者败之，执者失之。是以圣人无为，故无败，故无失。

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

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素 。

示例 1：

1
2
3
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

1
2
3
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

1
2
3
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

二分搜索法

这里用中间的值 nums[mid] 和右边界值 nums[right] 进行比较，若数组没有旋转或者旋转点在左半段的时候，中间值是一定小于右边界值的，所以要去左半边继续搜索，反之则去右半段查找，最终返回 nums[right] 即可。——来自grandyang

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

递归法

这里每次将区间 [start, end] 从中间 mid 位置分为两段，分别调用递归函数，并比较返回值，每次取返回值较小的那个即可，参见代码如下：

1
2
3
4
5
6
7
8
9
int findMin(vector<int>& nums) {
    return helper(nums, 0, (int)nums.size() - 1);
}

int helper(vector<int>& nums, int start, int end) {
    if (nums[start] <= nums[end]) return nums[start];
    int mid = (start + end) / 2;
    return min(helper(nums, start, mid), helper(nums, mid + 1, end));
}

154. 寻找旋转排序数组中的最小值 II

给你一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素 。

示例 1：

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

示例 2：

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

二分查找

当第一个数字和最后一个数字，还有中间那个数字全部相等的时候，将右指针左移一位（或者将左指针右移一位），略过一个相同数字，这对结果不会产生影响，因为只是去掉了一个相同的，然后对剩余的部分继续用二分查找法。——来自grandyang

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

递归法

不过写法跟之前那道略有不同，只有在 nums[start] < nums[end] 的时候，才能返回 nums[start]，等于的时候不能返回，比如 [3, 1, 3] 这个数组。

1
2
3
4
5
6
7
8
9
10
int findMin(vector<int>& nums) {
    return helper(nums, 0, (int)nums.size() - 1);
}

int helper(vector<int>& nums, int start, int end) {
    if (start == end) return nums[start];
    if (nums[start] < nums[end]) return nums[start];
    int mid = (start + end) / 2;
    return min(helper(nums, start, mid), helper(nums, mid + 1, end));
}

33. 搜索旋转排序数组

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid+1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

  • 如果 [l, mid-1] 是有序数组，且 target 的大小满足 [nums[l], nums[mid])，则我们应该将搜索范围缩小至 [l, mid-1]，否则在 [mid+1, r] 中寻找。
  • 如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1], nums[r]]，则我们应该将搜索范围缩小至 [mid+1, r]，否则在 [l, mid-1] 中寻找。

作者：LeetCode-Solution

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：nums = [1], target = 0
输出：-1

代码：

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

位我上者，灿烂星空；道德律令，在我心中。