讀完本文，你不僅學(xué)會(huì)了算法套路，還可以順便去 LeetCode 上拿下如下題目：
26.刪除排序數(shù)組中的重復(fù)項(xiàng)
-----------
我們知道對(duì)于數(shù)組來(lái)說(shuō)，在尾部插入、刪除元素是比較高效的，時(shí)間復(fù)雜度是 O(1)，但是如果在中間或者開(kāi)頭插入、刪除元素，就會(huì)涉及數(shù)據(jù)的搬移，時(shí)間復(fù)雜度為 O(N)，效率較低。
所以上篇文章 O(1)時(shí)間刪除/查找數(shù)組中的任意元素 就講了一種技巧，把待刪除元素交換到最后一個(gè)，然后再刪除，就可以避免數(shù)據(jù)搬移。
PS：我認(rèn)真寫(xiě)了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚(yú)得水了。
有序數(shù)組/鏈表去重
先講講如何對(duì)一個(gè)有序數(shù)組去重，先看下題目：
函數(shù)簽名如下：
int removeDuplicates(int[] nums);
顯然，由于數(shù)組已經(jīng)排序，所以重復(fù)的元素一定連在一起，找出它們并不難，但如果毎找到一個(gè)重復(fù)元素就立即刪除它，就是在數(shù)組中間進(jìn)行刪除操作，整個(gè)時(shí)間復(fù)雜度是會(huì)達(dá)到 O(N^2)。
PS：我認(rèn)真寫(xiě)了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚(yú)得水了。
簡(jiǎn)單解釋一下什么是原地修改：
如果不是原地修改的話，我們直接 new 一個(gè) int[] 數(shù)組，把去重之后的元素放進(jìn)這個(gè)新數(shù)組中，然后返回這個(gè)新數(shù)組即可。
但是原地刪除，不允許我們 new 新數(shù)組，只能在原數(shù)組上操作，然后返回一個(gè)長(zhǎng)度，這樣就可以通過(guò)返回的長(zhǎng)度和原始數(shù)組得到我們?nèi)ブ睾蟮脑赜心男┝恕?/p>
這種需求在數(shù)組相關(guān)的算法題中時(shí)非常常見(jiàn)的，通用解法就是我們前文 雙指針技巧 中的快慢指針技巧。
我們讓慢指針 slow 走在后面，快指針 fast 走在前面探路，找到一個(gè)不重復(fù)的元素就告訴 slow 并讓 slow 前進(jìn)一步。這樣當(dāng) fast 指針遍歷完整個(gè)數(shù)組 nums 后，nums[0..slow] 就是不重復(fù)元素。
int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// 維護(hù) nums[0..slow] 無(wú)重復(fù)
nums[slow] = nums[fast];
}
fast++;
}
// 數(shù)組長(zhǎng)度為索引 + 1
return slow + 1;
}
看下算法執(zhí)行的過(guò)程：
再簡(jiǎn)單擴(kuò)展一下，如果給你一個(gè)有序鏈表，如何去重呢？這是力扣第 83 題，其實(shí)和數(shù)組去重是一模一樣的，唯一的區(qū)別是把數(shù)組賦值操作變成操作指針而已：
ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.val != slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// 斷開(kāi)與后面重復(fù)元素的連接
slow.next = null;
return head;
}
移除元素
這是力扣第 27 題，看下題目：
函數(shù)簽名如下：
int removeElement(int[] nums, int val);
題目要求我們把 nums 中所有值為 val 的元素原地刪除，依然需要使用 雙指針技巧 中的快慢指針：
如果 fast 遇到需要去除的元素，則直接跳過(guò)，否則就告訴 slow 指針，并讓 slow 前進(jìn)一步。
這和前面說(shuō)到的數(shù)組去重問(wèn)題解法思路是完全一樣的，就不畫(huà) GIF 了，直接看代碼：
int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
注意這里和有序數(shù)組去重的解法有一個(gè)重要不同，我們這里是先給 nums[slow] 賦值然后再給 slow++，這樣可以保證 nums[0..slow-1] 是不包含值為 val 的元素的，最后的結(jié)果數(shù)組長(zhǎng)度就是 slow。
PS：我認(rèn)真寫(xiě)了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚(yú)得水了。
移動(dòng)零
這是力扣第 283 題，我來(lái)描述下題目：
給你輸入一個(gè)數(shù)組 nums，請(qǐng)你原地修改，將數(shù)組中的所有值為 0 的元素移到數(shù)組末尾，函數(shù)簽名如下：
void moveZeroes(int[] nums);
比如說(shuō)給你輸入 nums = [0,1,4,0,2]，你的算法沒(méi)有返回值，但是會(huì)把 nums 數(shù)組原地修改成 [1,4,2,0,0]。
結(jié)合之前說(shuō)到的幾個(gè)題目，你是否有已經(jīng)有了答案呢？
題目讓我們將所有 0 移到最后，其實(shí)就相當(dāng)于移除 nums 中的所有 0，然后再把后面的元素都賦值為 0 即可。
所以我們可以復(fù)用上一題的 removeElement 函數(shù)：
void moveZeroes(int[] nums) {
// 去除 nums 中的所有 0
// 返回去除 0 之后的數(shù)組長(zhǎng)度
int p = removeElement(nums, 0);
// 將 p 之后的所有元素賦值為 0
for (; p < nums.length; p++) {
nums[p] = 0;
}
}
// 見(jiàn)上文代碼實(shí)現(xiàn)
int removeElement(int[] nums, int val);
至此，四道「原地修改」的算法問(wèn)題就講完了，其實(shí)核心還是快慢指針技巧，你學(xué)會(huì)了嗎？
相關(guān)推薦：
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書(shū) 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對(duì)應(yīng)的 GitHub 算法倉(cāng)庫(kù) 已經(jīng)獲得了 70k star，歡迎標(biāo)星！
