每天一道leetcode-81

2019 年 10 月 4 日
筆記

前言

目前準備每天刷一道題leetcode的題目，以此來激勵那些零基礎入門的人，千萬不要被什麼科班和非科班的說法嚇倒了，電腦這個行業只要你肯努力，沒有什麼逾越不了的鴻溝。

只要你肯努力，一份努力，一份汗水，在程式設計師這個職業，你的每一份付出都會得到對應的那一份彙報，尊重學習規律，循序漸進，別想著一口吃個胖子，羅馬也不是一天建成的，有朝一日，你終會變成你想成為的人。

題目目前可能需要一定的演算法與數據結構基礎才能看懂，後序會寫一下零基礎也能看懂的入門知識，然後就可以看懂我編寫的題目了~

案例

題目

leetcode-81 在有重複數字的有序數組中尋找n

tag(分類）: 二分查找這一類

鏈接：

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

題目詳述

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。

( 例如，數組 [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 可能包含重複元素。
這會影響到程式的時間複雜度嗎？會有怎樣的影響，為什麼？

題解

先上程式碼~

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

上一篇題目:每天一道leetcode-33

本道題目是對上一篇題目的加強版，在有序數組的中加入了有重複數字這一條件，題目變得稍微難了一些些，思路也是很類似的，就是分情況討論。

對於這種題目，數組，有序這兩個字眼結合起來，就是要第一時間考慮到二分查找。

先舉個例子，假設有旋轉數組[3,3,3,4,5,6,1,2,3,3],以圖形化的方式表示出這個數組，3,3,3,4,5,6為前半段，1,2,3,4為後半段，後續的圖不是這個數組。

思路：由於無法確定target,nums[mid]誰大誰小，以及target和nums[mid]到底在前半段，還是在後一段，不同的情況下，對於令left = mid+1還是right = mid-1是不一樣的情況，所以這裡分情況進行討論，把所有的情況討論一遍，然後就知道，到底是變化left還是變化right，進而去縮小這個區間，找到我們要找到的數,在這裡唯一不同的就是多了一種nums[mid]與nums[left]如果相等了的情況，該怎麼處理。

nums[mid] >nums[left]

第10行，nums[mid]>nums[left]判斷為真，說明nums[mid]在前半段。如下圖所示