每天一道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在前半段，一種是在後半段，如下兩圖所示