33/153-搜索旋转排序数组

LeetCode

发布日期: 2022-02-21

LeetCode 33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with $O(log n)$ runtime complexity.

Example 1:

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

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

method：二分法

mid有2种情况，每种情况中target也有2种情况

mid在左分支
1. target在mid的左边，不能超出nums[0]
2. target在mid的右边
mid在右分支
1. target在mid的右边，不能超出nums[n-1]
2. target在mid的左边

int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target) return mid; 
        if (nums[mid] >= nums[0]) { // mid在左分支
            if (target >= nums[0] && target < nums[mid]) {
                r = mid - 1;    // target在mid左边
            }
            else {
                l = mid + 1;    // target在mid右边
            }
        }
        else {  // mid在右分支
            if (target <= nums.back() && target > nums[mid]) {
                l = mid + 1;    // target在mid右边
            }
            else {
                r = mid - 1;    // target在mid左边
            }
        }
    }
    return -1;
}

时间复杂度：$O(logn)$
空间复杂度：$O(1)$

LeetCode 81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

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

示例 2：

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

method

类似出现重复的数字，不能判断哪边是递增的，哪边是递减的，所以就直接缩小范围

bool search(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (nums[mid] == target) return true;
        if (nums[mid] == nums[l] && nums[mid] == nums[r]) {
            l++;
            r--;	// 缩小范围
        } else if (nums[mid] >= nums[l]) {
            if (target >= nums[l] && target < nums[mid]) r = mid - 1;
            else l = mid + 1;
        } else {
            if (target > nums[mid] && target <= nums[r]) l = mid + 1;
            else r = mid - 1;
        }
    }
    return false;
}

面试题 10.03. 搜索旋转数组

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例1:

输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）

示例2:

输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出：-1 （没有找到）

method

在81题的基础上，增加了元素可以重复，并且要找的是第一个等于target的位置

同样需要判断元素相等时缩小范围

int search(vector<int>& arr, int target) {
    int l = 0, r = arr.size() - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (arr[l] == target) return l;	// 左边界找到了直接返回
        if(arr[mid] == target) {
            r = mid;
        } else if (arr[mid] > arr[l]) {
            if (target >= arr[l] && target < arr[mid]) r = mid - 1;
            else l = mid + 1;
        } else if (arr[mid] < arr[l]) {
            if (target > arr[mid] && target <= arr[r]) l = mid + 1;
            else r = mid - 1;
        } else l++;	// 和左边界相等就直接移动左边界缩小范围
    }
    return -1;
}

LeetCode 153. Find Minimum in Rotated Sorted Array

LeetCode-153

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array a[0], a[1], a[2], ..., a[n-1] 1 time results in the array a[n-1], a[0], a[1], a[2], ..., a[n-2].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in $O(logn)$ time.

Example 1:

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

method: 二分模板一

如果当前元素比nums[0]小，说明是在最小值的分支上，r往左移
否则就是在nums[0]分支上，l要往右移
如果最后一个元素比nums[0]大，说明没有旋转，直接返回第一个就可以

int findMin(vector<int>& nums) {
    if (nums[0] < nums.back()) return nums[0];
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (nums[mid] < nums[0]) r = mid;
        else l = mid + 1;
    }
    return nums[r];
}

时间复杂度：$O(logn)$
空间复杂度：$O(1)$

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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

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

你必须尽可能减少整个过程的操作步骤。

示例 1：

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

示例 2：

输入：numbers = [[10,1,10,10,10]]
输出：1

method

在上一题的基础上增加难度，元素可以重复

如果是nums[mid]=nums[r]，并不能确定最小值在mid的哪一边，但是r可以往左移，反正mid的值等于r的值，就算nums[r]是最小值也没关系

int minArray(vector<int>& nums) {
    if (nums[0] < nums.back()) return nums[0];
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (nums[mid] < nums[r]) r = mid;
        else if (nums[mid] > nums[r]) l = mid + 1;
        else r--;
    }
    return nums[l];
}