每天一道leetcode-33

• 2019 年 10 月 4 日
• 筆記

前言

目前准备每天刷一道题leetcode的题目，以此来激励那些零基础入门的人，千万不要被什么科班和非科班的说法吓倒了，计算机这个行业只要你肯努力，没有什么逾越不了的鸿沟。

只要你肯努力，一份努力，一份汗水，在程序员这个职业，你的每一份付出都会得到对应的那一份汇报，尊重学习规律，循序渐进，别想着一口吃个胖子，罗马也不是一天建成的，有朝一日，你终会变成你想成为的人。

题目目前可能需要一定的算法与数据结构基础才能看懂，后序会写一下零基础也能看懂的入门知识，然后就可以看懂我编写的题目了~

案例

题目

leetcode33 在旋转数组中查找一个数n

tag(标签）：二分查找

原题链接：

https://leetcode.com/problems/search-in-rotated-sorted-array/

题目详述

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

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

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

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

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

示例 1:

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

示例 2:

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

题解

先上代码，准备结合着代码进行讲解。

class Solution {      public int search(int[] nums, int target) {          if(nums.length == 0)              return -1;          int left = 0;          int right = nums.length - 1;          while(left <= right)          {              int mid = left + (right-left)/2;              if(nums[mid] == target)                  return mid;              else if(nums[left] == target)                  return left;              else if(nums[right] == target)                  return right;              else{                  if(target > nums[mid])                  {//1                      if(nums[mid] > nums[0])                      {//2                          left = mid + 1;                      }else                      {                          if(target > nums[0])//3                              right = mid - 1;                          else                              left= mid + 1;                      }                  }                  else{                      if(nums[mid] > nums[0])                      {//4                          if(target < nums[0])//5                              left = mid + 1;                          else                              right = mid - 1;                      }                      else{                          right = mid - 1;                      }                  }              }          }          return -1;      }  }  

对于这种题目，数组，有序这两个字眼结合起来，就是要第一时间考虑到二分查找。不懂什么是二分查找的参考我的这篇文章。RNG输了，但我们不能输

假设有这样一个旋转数组[4,5,6,7,8,0,1,2,3],我用图形化的方式表示为下图，方便大家理解，前一段代表4,5,6,7,8，后一段代表0,1,2,3。

下图只是一种情况，后序有多种情况，后序不再是这个数组。

思路：由于无法确定target,nums[mid]谁大谁小，以及target和nums[mid]到底在前半段，还是在后一段，不同的情况下，对于令left = mid+1还是right = mid-1是不一样的情况，所以这里分情况进行讨论，把所有的情况讨论一遍，然后就知道，到底是变化left还是变化right，进而去缩小这个区间，找到我们要找到的数。

target>nums[mid]

情况1

在第18行上，target大于nums[mid]时，紧接着19行，继续讨论nums[mid]与nums[0]的情况，当nums[mid]大于nums[0],也就是说明了nums[mid]一定在前半段，而target是大于nums[mid]的，target必然在前半段，所以这个时候肯定就是要把left=mid+1 才可以去逼近这个target.

情况2

当target大于nums[mid]时候，19行判断后发现nums[mid]小于nums[0],所以这时候，nums[mid]必然在后半段。而targe是大于nums[mid],但target大于nums[mid]的话有两种情况，一种是target在前半段，一种是在后半段，如下两图所示

上图就是target在前半段的情况，也就是代码24行的判断target>nums[0]，这个时候，看图，得知应该是right=mid-1,向target逼近！

上图就是target在后半段的情况，在代码24行判断不成立，看图得知应该left=mid+1,向target逼近。

target<nums[mid]

情况3

在代码17行判断返回false,也就是target<nums[mid]这个大前提下。进入到30行代码。

进入到31行代码，当nums[mid] > nums[0],mid在前半段，而target是小于nums[mid],target不知道是在前半段，还是在后半段，所以得分情况讨论

target在后半段 target<nums[0]

看上面图，明显应该是left = mid + 1;向target逼近；

target在前半段target>nums[0]

上图显示，明显应该是right=mid-1;

情况4

当代码31判断为假，那么进入38行。也就是nums[mid]在后半段。

而大前提是target小于nums[mid],所以target必然在后半段。

如上图所示，所以right=mid-1,去逼近target。

结束语

以上就是我的思路，把所有的情况自己心里面想清楚，我感觉是用笔画图好一些，更加的清晰明了，自己把所有的情况知道以后，那么写起来就下笔如有神了。

END