A.每日一题：33. 搜索旋转排序数组

题目链接33. 搜索旋转排序数组中等算法原理解法二分查找0ms击败100.00%时间复杂度O(log n)1.确定偏移量我们可以通过最小的元素来找到偏移量因为最小的元素本应该在下标0的位置只要找到偏移后的位置k那么我们完全可以将题述的“左转逻辑”看成“右转k个的逻辑”这个过程我们有两种做法①从头遍历到尾找到最小值进而确定其下标→时间复杂度O(N)这种写法在下面的附加题上有体现②直接照搬 优选算法-二分23.搜索旋转排序数组中的最小值 →时间复杂度O(log n)2.二分查找我们直接用二分查找的最左端点模型或者最右端点模型来找到目标值target找到了返回对应下标找不到返回1但是这里有个细节二分查找需要基于二段性此题也就是需要有序的数组我们怎么保证在log n的复杂度下使用二分查找呢可以使用下标映射的关系找到映射下标index(midk)%n这样就可以映射到原有序的数组了最后返回的时候也用index(midk)%n下标的值来分析返回值JAVA代码class Solution { //33. 搜索旋转排序数组 public int search(int[] nums, int target) { //找到偏移量可以看成向右旋转k个 int kfindMin(nums); int nnums.length; int left0,rightn-1; while(leftright){ int midleft(right-left)/2; //找到原有序数组时的下标 int index(kmid)%n; if(nums[index]target) leftmid1; else rightmid; } int index(leftk)%n; return nums[index]target?index:-1; } //153. 寻找旋转排序数组中的最小值 private int findMin(int[] nums){ int left0,rightnums.length-1; //如果没有旋转第一个就是最小元素 if(nums[left]nums[right]) return 0; while(leftright){ int midleft(right-left1)/2; if(nums[mid]nums[0]) rightmid-1; else leftmid; } return left1; } }附加题题目链接1752. 检查数组是否经排序和轮转得到简单算法原理如果这道题没有重复元素的话可以类比上题的思路写成下面的代码⬇️class Solution { //1752. 检查数组是否经排序和轮转得到 public boolean check(int[] numsA) { int nnumsA.length; //找到偏移量x int xfindMin(numsA); int[] numsBnumsA.clone(); Arrays.sort(numsB); for(int i0;in;i){ //找到当前位置经排序和轮转应该得到的下标 int id(ix)%n; if(numsB[i]!numsA[id]) return false; } return true; } //寻找最小值对应的下标 private int findMin(int[] nums){ int minnums[0]; int index0; for(int i1;inums.length;i){ if(nums[i]min){ minnums[i]; indexi; } } return index; } }通过从头遍历到尾找到最小值进而确定其下标然后再对比原升序数组看每个元素能否对应上从而判断数组是否可以经排序和轮转得到但是因为重复元素的出现这种方法就不可取了解法一次遍历0ms击败100.00%时间复杂度O(N)这题其实也没有那么麻烦根据题意如果nums是由一个递增数组旋转得到的那么nums至多有两个递增段也就是说nums至多有一对相邻元素是严格递减的即nums[i-1]nums[i]至多出现一次上述过程我们可以用一个boolean类型的sorted进行标记此外如果有两个递增段第二段的最大值不能超过第一段的最小值即nums[0]≥nums[n-1]JAVA代码class Solution { //1752. 检查数组是否经排序和轮转得到 public boolean check(int[] nums) { int nnums.length; boolean sortedtrue; for(int i1;in;i){ if(nums[i-1]nums[i]){//严格递减 //如果之前出现过严格递减说明至少有三个递增段 if(!sorted) return false; sortedfalse; } } return sorted||nums[0]nums[n-1]; } }