2020-05-05 15:35 字节跳动_互娱研发_Android开发

关注

LeetCode 【33. 搜索旋转排序数组】要是看不懂，我就去出家

写在前面：

不要单纯为了做题而做题！培养思维，举一反三很重要！

今天通过一道非常经典的 LeetCode 题《搜索旋转排序数组》，来和大家一步步的，重温 二分查找 的基本套路和该类题的思路。相关博文：

https://blog.csdn.net/u011489043/article/details/78683856

欢迎大佬关注在下的微信公众号“张氏文画”，不光有新鲜的 LeetCode 题解（多种思路，包教包会，开拓思维），还有经典的文章及短视频和大家分享，一起嘿嘿嘿
图片说明

题目描述：

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

测试用例：

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

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

难度等级：

Medium

思路一：

暴力求解，直接遍历

代码：

时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

Result：

Runtime：0ms

Your runtime beats 100% of java submissions.

思路二：

将旋转后的有序数组，分为左右两个有序数组，分别进行二分查找就可以了。需要查找出转折点

代码：

时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int temp_position = 0;
        for(int i = 0; i < nums.length - 1; i++) {
            if(nums[i] > nums[i+1]) {
                temp_position = i;
            }
        }

        // 对左右有序数组依次进行二分查找
        int low = 0;
        int high = temp_position;
        while(low <= high){
            int mid = low + (high - low) / 2;
            if (nums[mid] > target) {
                high = mid - 1;
            } else if (nums[mid] == target) {
                return mid;
            } else {
                low = mid + 1;
            }

            // 当左边有序数组没查找到目标值时，开始折半查找右边数组。
            if(low > high) {
                low = temp_position + 1;
                high = nums.length - 1;
                temp_position = nums.length; // 控制最多进行两次二分查找，不会进入死循环
            }
        }
        return -1;
    }
}

Result：

Runtime：1ms

Your runtime beats 42.87% of java submissions.

思路三：

思路二本质上时间复杂度还是O(n)。所以需要使用改进的二分查找。

思路就是：从题目中我们可以得到，当旋转完数组后，必有数组的一部分仍然保持有序。比如，对于数组[6 7 1 2 3 4 5]，顺序从7到1打乱。所以当我们使用二分法时，就可以做个判断即哪部分是有序的并且判断目标值是否在那部分数组中；如果没在，则继续查找另一部分。

代码：

时间复杂度O(logn)，空间复杂度O(1)

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int low = 0;
        int high = nums.length - 1;
        while(low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if(nums[low] <= nums[mid]) {
                if(target >= nums[low] && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                if(target > nums[mid] && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }     
            }
        }
        return nums[low] == target ? low : -1;
    }
}

Result：

Runtime：0ms

Your runtime beats 100% of java submissions.

思路四：

其实，根据题意，按照升序排序的数组在预先未知的某个点上进行了旋转，可得

如果nums[0] <= nums[i]，说明数组[0...i]是有序的，所以如果满足nums[0] <= target <= nums[i]，我们就应该在[0...i]范围内继续查找；
如果nums[i] < nums[0]，说明数组[0...i]之间包含一个下降沿，即旋转的位置所在。所以在数组的[i+1...end]必是有序的。所以如果目标值不在该范围内，我们就应该在[0...i]内继续寻找，即 target <= nums[i] < nums[0] 或者 nums[i] < nums[0] <= target

总结这三种情况:

nums[0] <= target <= nums[i]

target <= nums[i] < nums[0]

nums[i] < nums[0] <= target

所以现在有三个判断，我们需要知道其中的哪两个为true。又因为这三者不可能同时为true，所以我们只需要判断“其中两个true”和“其中一个true”。要实现这个判断，利用奇偶性（异或）即可。

代码：

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid])) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
            // System.out.println("lo = "+lo+" hi = "+hi+" mid = "+mid);
            // System.out.println("ee = "+(nums[0] > target)+" ff = "+(nums[0] > nums[mid])
                    //+" gg = "+(target > nums[mid]));
        }
        return lo == hi && nums[lo] == target ? lo : -1;
    }
}

Result：

Runtime：0ms

Your runtime beats 100% of java submissions.

大佬们，记得随手关注下我的公众号哦！，一起嘿嘿嘿
图片说明

------致所有正在努力奋斗的程序猿们！加油！！
有码走遍天下 ***寸步难行
1024 - 梦想，永不止步!
爱编程不爱Bug
爱加班不爱黑眼圈
固执但不偏执
疯狂但不疯癫
生活里的菜鸟
工作中的大神
身怀宝藏，一心憧憬星辰大海
追求极致，目标始于高山之巅
一群怀揣好奇，梦想改变世界的孩子
一群追日逐浪，正在改变世界的极客
你们用最美的语言，诠释着科技的力量
你们用极速的创新，引领着时代的变迁

——乐于分享，共同进步，欢迎留言讨论
——Treat Warnings As Errors
——Any comments greatly appreciated
——Talking is cheap, show me the code