汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

搜索旋转排序数组(系列)

发表于 更新于 分类于 Valine：
本文字数： 6k 阅读时长 ≈ 5 分钟

33. 搜索旋转排序数组

整数数组 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,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

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

 

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

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

示例 3：
输入：nums = [1], target = 0
输出：-1

python语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums)-1
        # 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
        # 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
        while low <= high:
            mid = low + (high-low)//2
            print('low,high,mid', low, high, mid)
            if nums[mid] == target:
                return mid
            elif nums[low] <= nums[mid]:
                # 左半有序 且目标值在左部分
                if nums[low] <= target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            else:
                # 右半有序 且目标值在右部分
                if nums[high] >= target > nums[mid]:
                    low = mid + 1
                else:
                    high = mid - 1
        return -1

go语言

go的执行效率比python真是高太多了

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
func search(nums []int, target int) int {
    low, high := 0, len(nums)-1
    // 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
    // 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
    // fmt.Println(low, high)
    // print(low, high)
    for low <= high{
        mid := low + (high-low)/2
        // fmt.Println(low, mid, highc)
        if nums[mid] == target{
            return mid
        }else if nums[low] <= nums[mid]{    //左半数组有序, 注意<=
            if nums[low] <= target && target < nums[mid]{
                high = mid - 1
            }else{
                low = mid + 1
            }
        }else{
            if nums[high] >= target && target > nums[mid]{
                low = mid + 1
            }else{
                high = mid - 1
            }
        }
        // fmt.Println("-----", low, mid, high)
    }
    return -1

}

C++

旋转后，每次二分的时候，一定会得到一半是有序一半是无序的数组，如果目标值落在有序部分，则可以按照经典二分处理，否则在无序部分再二分

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 search(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        while (low <= high) {
            int mid = low + (high-low)/2;
            if (target == nums[mid]) {
                return mid;
            }else if (nums[low] <= nums[mid]) {
                // 结果在左半边有序的这部分，注意包含左边界
                if (nums[low] <= target && target < nums[mid]) {
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }else{
                // 结果在右半边有序的这部分，注意包含右边界
                if (nums[mid] < target && target <= nums[high]) {
                    low = mid + 1;
                }else{
                    high = mid - 1;
                }
            }
        }
        return -1;
    }
};

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

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
31
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        while (low <= high) {
            int mid = low + (high-low)/2;
            if (target == nums[mid]) {
                return true;
            // 核心在于 如果有重复的数，可能导致无法判断哪边是有序的
            }else if (nums[low] == nums[mid] && nums[high] == nums[mid]){
                low++;
                high--;
            }else if (nums[low] <= nums[mid]) {
                // 结果在左半边有序的这部分，注意包含左边界
                if (nums[low] <= target && target <= nums[mid]) {
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }else{
                // 结果在右半边有序的这部分，注意包含右边界
                if (nums[mid] <= target && target <= nums[high]) {
                    low = mid + 1;
                }else{
                    high = mid - 1;
                }
            }
        }
        return false;
    }
};

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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1：

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

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

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

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findMin(vector<int>& nums) {
        int ans = INT_MAX;
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right-left)/2;
            // 左边有序，left即为左边最小值，需要去右边找
            if (nums[left] <= nums[mid]) {
                ans = min(ans, nums[left]);
                left = mid + 1;
            }else{
                // 右边有序，mid即为右边最小值，需要去左边找
                ans = min(ans, nums[mid]);
                right = mid - 1;
            }
        }
        // cout << left << " " << right << endl;
        return ans;


    }
};

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：

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

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

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

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
class Solution {
public:
    int findMin(vector<int>& nums) {
        int ans = INT_MAX;
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right-left)/2;
            // 重复数字会导致无法判断左右哪边是否有序
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                ans = min(ans, nums[mid]);
                left++;
                right--;
            }else if (nums[left] <= nums[mid]) {
                ans = min(ans, nums[left]);
                left = mid + 1;
            }else{
                ans = min(ans, nums[mid]);
                right = mid - 1;
            }
        }
        return ans;


    }
};

还有一种逐渐逼近的思路，但是容易出错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findMin(vector<int>& nums) {
        int ans = INT_MAX;
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            // 如果全局有序，直接返回
            if (nums[left] < nums[right]) return nums[left];
            int mid = left + (right-left)/2;
            // 重复数字会导致无法判断左右哪边是否有序
            if (nums[left] == nums[mid]) {
                left++;
            // 如果左边有序，由于全局无序，则右边必无序，最小值在右边
            }else if (nums[left] < nums[mid]) {
                left = mid + 1;
            // 左边无序，右边有序，mid即为右边最小值
            }else{
                right = mid;
            }
        }
        // cout << left << " " << right;
        return nums[right];
    }
};
坚持原创分享，您的支持将鼓励我继续创作

欢迎关注我的其它发布渠道

------------- 本文结束,感谢阅读 如有问题可留言交流 -------------