704. 二分查找 - 力扣（LeetCode）

關于二分查找

• 最重要的是要處理好邊界問題，每次寫完邊界可以帶入特殊值進行測試
• 確定區間的不變量是什么？比如區間的左閉右閉，和左閉右開，每次二分完的新區間，一定要一直和最開始的區間的定義保持一致，要時刻明確區間的含義
• 注意二分的幾種情況（當數組長度為n的情況下）
  • 當l = 0, r = n的時候因為r這個值我們在數組中無法取到,while(l < r) 是正確寫法
  • 當l = 0, r = n - 1的時候因為r這個值我們在數組中可以取到,while(l <= r) 是正確寫法 主要看能不能取到這個值
• 注意處理二分mid溢出的問題
  • 當l 和 r 較大時，mid = (l + r) / 2 可能會出現大于INT_MAX的情況,會溢出。
  • 可以寫成 mid = l + (r - l) / 2? 或者 mid = l + ((r - l) >>1)的形式

思路：這道題目的前提是數組為有序數組，同時題目還強調數組中無重復元素，因為一旦有重復元素，使用二分查找法返回的元素下標可能不是唯一的，這些都是使用二分法的前提條件，當大家看到題目描述滿足如上條件的時候，可要想一想是不是可以用二分法了。

一開始的代碼：

class Solution {
public:int search(vector<int>& nums, int target) {int size = nums.size();int l = 0, r = size - 1;while(l < r){int mid = (l + r) >> 1;if(nums[mid] < target)l = mid+1;elser = mid;}if(nums[r] != target)return -1;return r;}
};

這個代碼可以解決數組中存在重復元素的情況，但是要注意的點有許多，第一個 l < r 當我寫成 l <= r 時會死循環，因為當r = l時，進去循環，會一直r = mid 不能跳出循環，導致死循環還是要注意，這可能是不規范的寫法吧。

下面有兩個規范的模版（只能用于嚴格的升序排序，不能出現相同的元素，如果目標元素出現多次就不能正確的返回下標）

左閉右閉

class Solution {
public:int search(vector<int>& nums, int target) {int size = nums.size();int l = 0, r = size - 1;while(l <= r){int mid = l + ((r - l) >> 1);if(nums[mid] < target)//mid 小于就去mid的右面去找，并且mid不為targetl = mid+1;else if(nums[mid] > target)//mid 大于就去mid的左面去找，并且mid不為targetr = mid-1;else//就是 mid = target 的情況，所以直接返回mid就可以了return mid;}//沒有在循環中返回說明，沒有找到目標，返回-1return -1;}
};

左閉右開

class Solution {
public:int search(vector<int>& nums, int target) {int size = nums.size();int l = 0, r = size;while(l < r)    // r不能取到，l = r 沒有意義{int mid = l + ((r - l) >> 1);if(nums[mid] < target)//mid 小于就去mid的右面去找，并且mid不為targetl = mid+1;else if(nums[mid] > target)//mid 大于就去mid的左面去找，并且mid不為target，但是區間不包含mid 所以 r = midr = mid;else//就是 mid = target 的情況，所以直接返回mid就可以了return mid;}//沒有在循環中返回說明，沒有找到目標，返回-1return -1;}
};

其實二分還有很多應用場景，有著許多變體，比如說查找第一個大于target的元素或者第一個滿足條件的元素，都是一樣的，根據是否滿足題目的條件來縮小答案所在的區間，這個就是二分的本質。另外需要注意，二分的使用前提：有序數組

27. 移除元素 - 力扣（LeetCode）

?我的思路（對撞指針）

????????題目要求返回不等于val的個數和nums數組，我們只需要考慮返回數組前面的部分是不等于val的就可以，所以這道題的解法是雙指針（對撞的），現從前面開始，如果不等于就走，等于之后 右指針在走，右指針找到不等于val的數字，與左指針指向的數字互換

class Solution {
public:int removeElement(vector<int>& nums, int val) {int l = 0, r = nums.size()-1;//如果為空直接返回0if(l > r)   return 0;while(l < r){if(nums[l] != val)l++;else{if(nums[r] != val){int tmp = nums[r];nums[r] = nums[l];nums[l] = tmp;}r--;}}//循環出來一定是 l = r 再判斷 l=r時等不等于valif(nums[l] == val)  //因為返回的是個數return l ;elsereturn l+1;}
};

暴力解：

一開始要求暴力解第一時間還真沒想到，后來看到題解，才想到的暴力解。

?數組中元素不能刪除只能進行覆蓋，所以暴力的解法就是從前往后遍歷，找到val然后用后面的元素將val進行覆蓋，同時將nums數組的長度減減，最后返回記錄好的數組長度就可以了。

class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for(int i = 0; i < size; i++){if(nums[i] == val){//val 后面的元素覆蓋val都向前進行覆蓋for(int j = i+1; j < size; j++){nums[j-1] = nums[j];}//交換之后，后面數組向前覆蓋，不知道后面數字是不是等于val然后要再一次判斷是不是等于vali--;//每覆蓋一次就要size--size--;}}return size;}
};

?雙指針（同向指針 \ 快慢指針）

快指針可以理解成在舊數組中找非目標元素，然后賦值給慢指針指向的新數組，雖然都指向一個數組

• 關于二分法和移除元素的共性思考 這兩題之間有點類似的，他們都是在不斷縮小 left 和 right 之間的距離，每次需要判斷的都是 left 和 right 之間的數是否滿足特定條件。對于「移除元素」這個寫法本質上還可以理解為，我們拿 right 的元素也就是右邊的元素，去填補 left 元素也就是左邊的元素的坑，坑就是 left 從左到右遍歷過程中遇到的需要刪除的數，因為題目最后說超過數組長度的右邊的數可以不用理，所以其實我們的視角是以 left 為主，這樣想可能更直觀一點。用填補的思想的話可能會修改元素相對位置，這個也是題目所允許的。
• ?fast < nums.size() 和 fast <= nums.size()-1 沒什么區別，那為什么第二個會在空數組時報數組越界的錯誤？ vector的size()函數返回值是無符號整數，空數組時返回了0，再減個一會溢出；變成一個很大的正數，nums[fast] 會發生 null pointer of type 'int' 異常。

雙指針法（快慢指針法）：?通過一個快指針和慢指針在一個for循環下完成兩個for循環的工作。

雙指針法（快慢指針法）在數組和鏈表的操作中是非常常見的，很多考察數組、鏈表、字符串等操作的面試題，都使用雙指針法。

定義快慢指針

• 快指針：尋找新數組的元素 ，新數組就是不含有目標元素的數組
• 慢指針：指向更新 新數組下標的位置

所以思路就是，快指針在前面尋找不是目標元素的元素，慢指針可以理解為用來維護新數組，也就是不含目標元素的數組，如果不等于val 快慢指針都++，等于慢指針用來記錄val的位置，快指針向后尋找不等于val的值與慢指針的val進行交換，直到快指針走到最后

class Solution {
public:int removeElement(vector<int>& nums, int val) {int l = 0, r = 0;//r 每一步都要走for(int i = r; i < nums.size(); i++){//可以理解為，i為一個符合條件的數組，不等于val就往里面加if(nums[i] != val)nums[l++] = nums[i];}// l 就為新數組的長度return l;}
};

?977. 有序數組的平方 - 力扣（LeetCode）

思路:看到這道題，我首先想到的是，將他們的平方都放入數組中，然后進行排序，這種時間復雜度比較高的暴力解法。后面自己想了一下可不可以使用一個時間復雜度為O（1）的方法解出來呢，一開始想用雙指針，每個分別用來記錄一個數組，比較然后先比較在插入，發現最后回到了插入排序的思想。

先看看暴力解法

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {for(int i = 0; i < nums.size(); i++){nums[i] = nums[i]*nums[i];}sort(nums.begin(), nums.end());return nums;}
};

?可以發現雖然通過了，但是方法還是不太好。

雙指針

? ? ? ? 我們發現有負數和正數，我們不能判斷負數和正數誰的平方誰更大（為什么判斷誰更大呢，因為數組是從小到大排的，負數越小平方就越大，看到這，我們可不可以先開一個一摸一樣大小的數組，然后用兩個指針分別記錄數組兩端平方較大的值呢，誰更大誰就先從后往前插入）

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int size =nums.size();int l = 0, r = nums.size()-1;//開一個新數組vector<int>a(nums.size());//x 用來為數組下標int x = size-1;while(l <= r){//右面大，右面賦值if(nums[l]*nums[l] < nums[r]*nums[r]){a[x--] = nums[r]*nums[r];r--;//指針向左移}    else{//左面大，左面賦值a[x--] = nums[l]*nums[l];//左指針右移l++;}}return a;}
};