每天一道leetcode154-寻找旋转排序数组(有重复数字)中的最小值
- 2019 年 10 月 4 日
- 筆記
前言
今天的题目是寻找旋转排序数组(有重复数字)中的最小值 II，这道题目是在之前做过的这道题目的升级版，这是上一道题目。
今天的题目是在上一道题目的基础上加了有重复数字这一条件，本次的题目是在上一次题目的基础上进行。
题目
leetcode-154 寻找旋转排序数组(有重复数字)中的最小值 II
分类（tag）:二分查找这一类；
难度：hard;
英文链接：
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
中文链接：
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
题目详述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1：
输入: [1,3,5]输出: 1
示例 2：
输入: [2,2,2,0,1]输出: 0
题目详解
思路
由于之前已经有了在不包含重复数字的代码，所以我想着尝试在这个代码的基础上，进行改进，直到成功AC。
第一次尝试
直接把上次在153题中的代码进行了提交，如果不懂下面的代码可以看我的这篇文章。
果然没有AC。
class Solution { public int findMin(int[] nums) { if(nums.length == 1) return nums[0]; if(nums.length == 2) return nums[0]<nums[1]?nums[0]:nums[1]; if(nums[0] < nums[nums.length-1]) return nums[0]; int left = 0; int right = nums.length - 1; while(left <= right) { int mid = left + (right-left)/2; if(mid>=1 && mid+1<nums.length && nums[mid] < nums[mid+1] && nums[mid] < nums[mid-1]) { return nums[mid]; }else if(left >= 1 && left+1<nums.length && nums[left] < nums[left-1] && nums[left] < nums[left+1]) { return nums[left]; }else if(right >= 1 && right+1<nums.length && nums[right] < nums[right-1] && nums[right] < nums[right+1]) { return nums[right]; } else if(nums[mid] > nums[0]) { left = mid + 1; }else{ right = mid - 1; } } return nums[0]<nums[nums.length-1]?nums[0]:nums[nums.length-1]; } }
这里的话，因为有重复数字，所以我把27行中else代表着nums[mid]<nums[0]的情况，而由于有重复数字，所以nums[mid]与nums[0]的情况应该分开讨论，单独列出来；
第二次尝试
class Solution { public int findMin(int[] nums) { if(nums.length == 1) return nums[0]; if(nums.length == 2) return nums[0]<nums[1]?nums[0]:nums[1]; if(nums[0] < nums[nums.length-1]) return nums[0]; int left = 0; int right = nums.length - 1; while(left <= right) { int mid = left + (right-left)/2; if(mid>=1 && mid+1<nums.length && nums[mid] < nums[mid+1] && nums[mid] < nums[mid-1]) { return nums[mid]; }else if(left >= 1 && left+1<nums.length && nums[left] < nums[left-1] && nums[left] < nums[left+1]) { return nums[left]; }else if(right >= 1 && right+1<nums.length && nums[right] < nums[right-1] && nums[right] < nums[right+1]) { return nums[right]; } else if(nums[mid] > nums[0]) { left = mid + 1; }else if(nums[mid] < nums[0]){ right = mid - 1; }else{ left++; } } return nums[0]<nums[nums.length-1]?nums[0]:nums[nums.length-1]; } }
如上述代码所示，增加了29行代码到31行代码，就是处理的nums[mid] 与nums[0]相等情况，由于当二者相等的时候，情况复杂，所以这个时候使用left++的方式去缩小查找的范围。
第三次尝试
上述代码，提交了以后，依然无法通过，下图中可以看出，这个测试用例没有过去，所以我就分析，自己手动地去跑一边代码，一开始left=0,right=5所以mid=2;
因为nums[mid]<nums[0]，所以可以看出来，nums[mid]是在旋转数组的后半段，进入到代码28行，right=mid-1,所以right=1;left=0;mid=0;
所以nums[mid]=nums[0],所以left++,left=1,right=1,mid=1,所以nums[mid]<nums[0].进入28行，right–,right=0，由于left>right,所以循环结束。
这个时候，我发现了，在靠近nums[0]的nums[1]的这个位置有可能是最小值，但是我的代码没有考虑到，类似的nums[nums.length-1]这个地方，靠近它的数组的前一个元素nums[nums.length-2]这个地方，也有可能是最小值，所以我在代码把这两种情况考虑了进去。如下述代码，33-40行代码就是我把刚才的两种情况考虑了进去。
class Solution { public int findMin(int[] nums) { if(nums.length == 1) return nums[0]; if(nums.length == 2) return nums[0]<nums[1]?nums[0]:nums[1]; if(nums[0] < nums[nums.length-1]) return nums[0]; int left = 0; int right = nums.length - 1; while(left <= right) { int mid = left + (right-left)/2; if(mid>=1 && mid+1<nums.length && nums[mid] < nums[mid+1] && nums[mid] < nums[mid-1]) { return nums[mid]; }else if(left >= 1 && left+1<nums.length && nums[left] < nums[left-1] && nums[left] < nums[left+1]) { return nums[left]; }else if(right >= 1 && right+1<nums.length && nums[right] < nums[right-1] && nums[right] <nums[right+1]) { return nums[right]; } else if(nums[mid] > nums[0]) { left = mid + 1; }else if(nums[mid] < nums[0]){ right = mid - 1; }else{ left++; } } int min = nums[0]; if(min > nums[nums.length-1]) min = nums[nums.length-1]; if(min > nums[1]) min = nums[1]; if(min > nums[nums.length-2]) min = nums[nums.length-2]; return min; } }
第四次尝试
上述代码提交以后，下图所示，还是没AC。
然后我根据上图显示，发现还有一种情况没有考虑进行，那就是最小值，出现在了中间的搜索过程中，所以我在上述代码中，在中间进行判断的过程中，把可能的最小值保存了下来。
下面代码中的27-28行代码，31-32行代码，35-36行代码，就是我把这种情况考虑了进去，保存中间可能出现的最小值。
class Solution { public int findMin(int[] nums) { if(nums.length == 1) return nums[0]; if(nums.length == 2) return nums[0]<nums[1]?nums[0]:nums[1]; if(nums[0] < nums[nums.length-1]) return nums[0]; int left = 0; int right = nums.length - 1; int min = nums[0]; while(left <= right) { int mid = left + (right-left)/2; if(mid>=1 && mid+1<nums.length && nums[mid] < nums[mid+1] && nums[mid] < nums[mid-1]) { return nums[mid]; }else if(left >= 1 && left+1<nums.length && nums[left] < nums[left-1] && nums[left] < nums[left+1]) { return nums[left]; }else if(right >= 1 && right+1<nums.length && nums[right] < nums[right-1] && nums[right] <nums[right+1]) { return nums[right]; } else if(nums[mid] > nums[0]) { if(nums[mid] < min) min = nums[mid]; left = mid + 1; }else if(nums[mid] < nums[0]){ if(nums[mid] < min) min = nums[mid]; right = mid - 1; }else{ if(nums[mid] < min) min = nums[mid]; left++; } } if(min > nums[nums.length-1]) min = nums[nums.length-1]; if(min > nums[1]) min = nums[1]; if(min > nums[nums.length-2]) min = nums[nums.length-2]; return min; } }
上述代码一提交，最终AC了。
结束语
罗马不是一日建成的，可以看到我这道题的AC过程，一步步地把没有考虑到的情况加入到我们的代码中，最后所有的情况考虑到了，那么自然也就能AC了。要学会使用错误用例来推敲问题到底出现在哪了，然后凭借着自己的死磕硬生生地把每一道题的代码都自己靠自己的努力去把它AC掉，不管写的多烂但起码是自己写的，这个就是我们编程的基本功的积累，当然如果超过半天都做不出来还是网上找找答案吧~
