LeetCode Notes_#81 搜索旋转排序数组II

LeetCode

Contents

• • 题目
  • 思路
  • 解答
  • 体会

题目

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

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

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 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

进阶:
这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

思路

• 这题与33题唯一的区别在于允许数字重复，那么每次进行二分搜索的时候，就无法判断中点的左边有序还是右边有序。如果nums[start] == nums[mid]，就直接忽略掉start,自增到start++重新判断。

思路图解

解答

1. class Solution { 
   

   ---

2. public boolean search(int[] nums, int target) { 
   

   ---

3. int len = nums.length; 
   

   ---

4. int start = 0; 
   

   ---

5. int end = len - 1; 
   

   ---

6. //ERROR:考虑输入为空的corner case 
   

   ---

7. if (len == 0) return false; 
   

   ---

8. //TIP:start,end相邻的时候，就已经可以结束了，防止再去计算mid，与start比较，会陷入死循环 
   

   ---

9. while(start + 1 < end){ 
   

   ---

10. //TIP:防止溢出,mid是负数 
    

    ---

11. //如果数字比较大，用mid = (start + end) / 2的写法就可能会溢出 
    

    ---

12. int mid = start + (end - start) / 2; 
    

    ---

13. if (nums[mid] == target) return true; 
    

    ---

14. if (nums[mid] == nums[start]) start++; 
    

    ---

15. if (nums[mid] > nums[start]){ 
    

    ---

16. //ERROR:这里不仅仅要和mid比大小，还要和start比大小 
    

    ---

17. if (nums[mid] > target && nums[start] <= target) end = mid; 
    

    ---

18. else start = mid; 
    

    ---

19. //ERROR:这里不能直接写else,否则nums[mid]==nums[start]时，也会进入这里边,三个分支一定是互斥的 
    

    ---

20. }else if(nums[mid] < nums[start]){ 
    

    ---

21. //ERROR:这里不仅仅要和mid比大小，还要和end比大小 
    

    ---

22. //为什么上边是和start比，这里是和end比？ 
    

    ---

23. //因为必须是在一个单调区间比较才有意义，这里已经确定了是在后一个单调区间，所以跟end比才有意义。start同理。 
    

    ---

24. if(nums[mid] < target && nums[end] >= target) start = mid; 
    

    ---

25. } 
    

    ---

26. } 
    

    ---

27. //TIP:由于在start和end相邻的时候已经终止循环了,所以循环结束后，要单独判定start/end 
    

    ---

28. //假如start+1==end时，依然进行二分搜索，mid == start,这时就不知道target在左侧还是右侧，只能直接判断 
    

    ---

29. if(nums[start] == target) return true; 
    

    ---

30. if(nums[end] == target) return true;  
    

    ---

31. //如果所有都执行完了，没有返回true,就是不在数组里边 
    

    ---

32. return false; 
    

    ---

33. } 
    

    ---

34. } 
    

    ---

这里在注释当中以标签的形式写了一些内容，ERROR代表我犯过的错误，TIP是技巧的总结。我发现与其单独写一段话描述代码思路，不如直接写在注释里，复习的话，直接看代码就完事了，方便。

体会

写笔记的目的不是为了好看，而是为了自己整理思路和回顾，所以反而随意一点（反正也不会有人看...），才能坚持下来，以前想着要把这个题解写的多么好，但是现实就是我目前还很菜，先能自己大概写一写，能进入一个刷题的良性循环才是王道，如果非要追求每题都自己搞清楚，太费时间，可能某一段时间比较闲，可以坚持住，那要是没有时间，这个习惯就会被抛弃。总的来说，要循序渐进。