LeetCode算法實戰 - - - 雙指針與移除元素、快慢指針與刪除有序數組中的重復項

第一題 - - - 移除元素
- 方法一 - - - 雙重循環
- 方法二 - - - 雙指針
- 方法三 - - - 相向雙指針（面對面移動）
第二題 - - - 刪除有序數組中的重復項
- 方法一 - - - 快慢指針
- 方法二 - - - 改進方法一
總結

💻作者簡介：曾與你一樣迷茫，現以經驗助你入門數據結構。
💡個人主頁：@笑口常開xpr 的個人主頁
📚系列專欄：硬核數據結構與算法
?代碼趣語：恰當的數據視圖實際上就決定了程序的結構。
💪代碼千行，始于堅持，每日敲碼，進階編程之路。
📦gitee 鏈接：gitee

在這里插入圖片描述

?????????在數據結構的世界里，每一種設計都可能孕育出驚人的效率變革。你是否深思過，一組精心組織的數據究竟能創造怎樣的奇跡？每一次挖掘底層原理，都是與計算機智慧的巔峰對話；每一次剖析存儲模式，都在破解數據世界的終極密碼。準備好迎接這場盛宴了嗎？讓我們一同探尋雙指針的無盡奧秘，見證它如何重塑數字時代的運行法則！

第一題 - - - 移除元素

移除元素

描述：給你一個數組 nums 和一個值 val，你需要原地移除所有數值等于 val 的元素。元素的順序可能發生改變。然后返回 nums 中與 val 不同的元素的數量。

?????????假設 nums 中不等于 val 的元素數量為 k，要通過此題，您需要執行以下操作：
1、更改 nums 數組，使 nums 的前 k 個元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
2、返回 k。

示例 1：
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2,,]
解釋：你的函數函數應該返回 k = 2, 并且 nums 中的前兩個元素均為 2。
示例 2：
輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3,,,_]
解釋：你的函數應該返回 k = 5，并且 nums 中的前五個元素為 0,0,1,3,4。

注意這五個元素可以任意順序返回。

提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

方法一 - - - 雙重循環

思路分析

?????????題目要求去除一組數中的重復元素，并且題目強調 nums 的其余元素和 nums 的大小并不重要。

?????????可以通過雙重循環遍歷數組，當發現目標值時，將其后的所有元素依次前移一位，從而覆蓋掉目標值元素。（類似順序表中的頭插）這樣做的目的是在原數組上直接進行元素移除操作，不使用額外的存儲空間，所以空間復雜度是 O(1)，時間復雜度是 O(N^2)。

溫馨提示：讀者們，先自己寫代碼，這是提升編程能力的好機會。若未達要求，別氣餒，參考下文解釋會有新收獲。

下面展示代碼示例。

int removeElement(int* nums, int numsSize, int val) 
{int i = 0;int count = 0;int temp1 = numsSize;while (i < temp1) {if (nums[i] == val) {int temp = i;while (temp < numsSize - 1) {nums[temp] = nums[temp + 1];temp++;}count++;temp1--;}else {i++;}}return numsSize - count;
}

注意

?????????網站上刷題分為 IO 型和接口型，IO 型是使用 scanf 得到輸入，結果使用 printf，并且要寫出完整程序。接口型是結果通過返回值返回，只寫實現的函數，是一部分程序。在 LeetCode 上刷題幾乎都是接口型，調試起來比較麻煩，牛客網中有 IO 型和接口型。

以數組元素為 3,2,2,3,1,2,4,2 val 為 2 進行動畫演示。

在這里插入圖片描述

方法二 - - - 雙指針

雙指針

?????????雙指針是一種常用的算法技巧，利用它們之間的相對移動來高效地解決問題，核心思想是將遍歷數組和原地修改分離，通過一次遍歷完成元素篩選和數組重構，通過指針的位置關系快速定位目標元素或區間。時間復雜度優化至 O(n)。

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

?????????同向即同一方向，兩個指針朝同一方向移動，速度可能不同（快指針步長更大，慢指針步長較小）。

思路分析

?????????題目要求刪除數組中等于 val 的元素，因此 輸出數組的長度一定小于等于輸入數組的長度，我們可以 把輸出的數組直接寫在輸入數組上。使用快指針 right 指向當前將要處理的元素，慢指針 left 指向下一個將要賦值的位置。

?????????如果快指針指向的元素不等于 val，它一定是輸出數組的一個元素，我們就將快指針指向的元素復制到慢指針位置，然后將快慢指針同時右移；

?????????如果快指針指向的元素等于 val，它不能在輸出數組里，此時左指針不動，右指針右移一位。

這里以示例 1 為例進行演示：

在這里插入圖片描述

溫馨提示：讀者們，先自己寫代碼，這是提升編程能力的好機會。若未達要求，別氣餒，參考下文解釋會有新收獲。

下面展示代碼示例。

int removeElement(int* nums, int numsSize, int val) 
{int left = 0;for (int right = 0; right < numsSize; right++) {if (nums[right] != val) {nums[left] = nums[right];left++;}}return left;
}

在這里插入圖片描述

時間復雜度：O(N)
空間復雜度：O(1)

方法三 - - - 相向雙指針（面對面移動）

特點

?????????兩個指針分別從數組的兩端出發，相向移動。

思路分析

?????????設左指針位于數組的首位，右指針位于數組的末尾，向中間移動遍歷該序列。如果左指針 left 指向的元素等于 val，此時將右指針 right 指向的元素復制到左指針 left 的位置，然后右指針 right 左移一位。如果賦值過來的元素恰好也等于 val，繼續把右指針 right 指向的元素的值賦值過來（左指針 left 指向的等于 val 的元素的位置繼續被覆蓋），直到左指針指向的元素的值不等于 val 為止。當左指針 left 和右指針 right 重合的時候，左右指針遍歷完數組中所有的元素。

這里以示例 1 為例進行演示：

在這里插入圖片描述

溫馨提示：讀者們，先自己寫代碼，這是提升編程能力的好機會。若未達要求，別氣餒，參考下文解釋會有新收獲。

下面展示代碼示例。

int removeElement(int* nums, int numsSize, int val)
{int left = 0, right = numsSize;while (left < right) {if (nums[left] == val) {nums[left] = nums[right - 1];right--;} else {left++;}}return left;
}

時間復雜度：O(N)
空間復雜度：O(1)

第二題 - - - 刪除有序數組中的重復項

描述：給你一個非嚴格遞增排列的數組 nums，請你原地刪除重復出現的元素，使每個元素只出現一次，返回刪除后數組的新長度。元素的相對順序應該保持一致。然后返回 nums 中唯一元素的個數。

?????????考慮 nums 的唯一元素的數量為 k，更改數組 nums，使 nums 的前 k 個元素包含唯一元素，并按照它們最初在 nums 中出現的順序排列。nums 的其余元素與 nums 的大小不重要。返回 k。

示例 1：
輸入：nums = [1,1,2]
輸出：2, nums = [1,2,_]
解釋：函數應該返回新的長度 2 ，并且原數組 nums 的前兩個元素被修改為 1, 2 。不需要考慮數組中超出新長度后面的元素。
示例 2：
輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數應該返回新的長度 5 ，并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。不需要考慮數組中超出新長度后面的元素。

方法一 - - - 快慢指針

思路分析：題目要求去除數組中的重復元素，并且題目強調使數組的前 k 個元素包含唯一元素，并按照它們最初在 nums 中出現的順序排列。可以使用雙指針的快慢指針求解這個問題，慢指針指向當前唯一元素，快指針遍歷數組，發現不同元素時更新慢指針。

溫馨提示：讀者們，先自己寫代碼，這是提升編程能力的好機會。若未達要求，別氣餒，參考下文解釋會有新收獲。

下面展示代碼示例。

int removeDuplicates(int* nums, int numsSize) 
{int left = 0;         //慢指針:指向當前無重復數組的最后位置int right = left + 1;        //快指針:從第二個元素開始遍歷while(right < numsSize)      //遍歷整個數組{if(nums[left] == nums[right]){right++;             //遇到重復元素，右移快指針}else{left++;              //找到新元素，更新慢指針位置nums[left] = nums[right]; //將新元素復制到慢指針位置}}return left + 1;  //返回無重復數組的長度（加上第1個元素）
}

空間復雜度是 O(1)
時間復雜度是 O(N)

方法二 - - - 改進方法一

?????????相較于方法 1，方法 2 對方法 1 進行了改進，改進如下：

邊界條件處理：
增加了 numsSize == 0 的判斷，避免空數組導致的未定義行為。
指針初始化優化：
left 和 right 均初始化為 1，因為第一個元素（索引 0）天然無需處理。
比較邏輯簡化：
通過比較 nums[right-1] 和 nums[right]，直接判斷當前元素是否與前一個重復。當發現不重復元素時，直接賦值到 left 位置，并遞增 left。

溫馨提示：讀者們，先自己寫代碼，這是提升編程能力的好機會。若未達要求，別氣餒，參考下文解釋會有新收獲。

下面展示代碼示例。

int removeDuplicates(int* nums, int numsSize) 
{if(numsSize == 0)           //處理空數組的邊界情況{return 0;}int left = 1;               //慢指針:從第二個位置開始寫入int right = 1;              //快指針:從第二個位置開始遍歷while(right < numsSize)     //遍歷整個數組{if(nums[right-1] != nums[right]) //當前元素與前一個不同{nums[left] = nums[right];   //將新元素寫入left位置left++;                     //移動left指針}right++;                    //無論如何都移動right指針}return left;                     //返回無重復數組的長度
}

時間復雜度是 O(N)
空間復雜度是 O(1)

在這里插入圖片描述

總結

?????????至此，關于雙指針的探索暫告一段落，但你的編程征程才剛剛啟航。編寫代碼是與計算機邏輯深度對話，過程中雖會在結構設計、算法實現的困境里掙扎，但這些磨礪加深了對代碼邏輯和數據組織的理解。愿你合上電腦后，靈感不斷，在數據結構的世界里持續深耕，書寫屬于自己的編程傳奇，下一次開啟，定有全新的精彩等待。小編期待重逢，盼下次閱讀時見證你們更大的進步，共赴代碼之約！