LeetCode26題：

github地址

有夢想的電信狗

前言

• 本文介紹用C++實現leetCode第26題
• 題目鏈接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

---

題目描述

---

題目與思路分析

目標分析：

1. 將數組中重復的元素移除，僅保留一份
2. 原地移除，意味著時間復雜度為O(n)，空間復雜度為O(1)
3. 返回nums中與唯一元素的個數

思路：雙指針

• src：指向待掃描元素，從第二個元素開始掃描
  • 因為第一個元素一定不是重復的，因此初始下標為1
• dst：dst下標及其之前，都是不重復的元素
  • dst指向不重復元素中的最后一個，初始下標為0
• count：記錄賦值的次數，賦值的次數即為除去第一個元素后，其余元素中的元素的種類，初始值為1

操作：

• 給定的數組是有序的，保證了我們不會遇到先前處理過的元素

• nums[src] != nums[dst] 時，說明：src位置的數第一次出現，將其放在dst的下一個位置。

  • dst先++，指向下一個不重復元素的位置
  • nums[dst] = nums[src]：向nums[dst]賦值放入元素，之后src++
  • 計數器count++

• nums[src] == nums[dst] 時，說明src位置的數之前出現過了，為重復元素，src++略過該元素。

代碼實現

• 時間復雜度：O(n)
• 空間復雜度：O(1)

class Solution {
public:int removeDuplicates(vector<int>& nums) {int src = 1, dst = 0;int count = 1;while(src < nums.size()){if(nums[src] == nums[dst]){++src;}else{++dst;nums[dst] = nums[src];++src;++count;}}return count;}
};

---

算法代碼優化

• 時間復雜度：O(n)
• 空間復雜度：O(1)

class Solution {
public:int removeDuplicates(vector<int>& nums) {int src = 1, dst = 0;int count = 1;while(src < nums.size()){if(nums[src] == nums[dst]){++src;}else{++dst;nums[dst] = nums[src];++src;++count;}}return count;}
};

通過觀察我們發現：

• 循環內dst和count自增的次數一樣，且初值分別為0和1，因此count == dst + 1
  • dst指向的是數組中不重復的最后一個元素，dst + 1即為不重復的元素的個數
• 且while循環內，if和else邏輯中，都執行了src++，因此if和else中的src++可以省略，直接將src在循環中++

class Solution {
public:int removeDuplicates(vector<int>& nums) {int src = 1, dst = 0;while(src < nums.size()){if(nums[src] != nums[dst]){++dst;nums[dst] = nums[src];}++src;}return dst + 1;}
};

• 利用前置和后置++的特性最終優化，雖然代碼更加簡潔了，但不推薦這么寫，因為算法的可讀性下降了

class Solution {
public:int removeDuplicates(vector<int>& nums) {int src = 1, dst = 0;while(src < nums.size()){if(nums[src] != nums[dst]){nums[++dst] = nums[src];}++src;}return dst + 1;}
};

---

以上就是本文的所有內容了，如果覺得文章對你有幫助，歡迎 點贊?收藏 支持！如有疑問或建議，請在評論區留言交流，我們一起進步

分享到此結束啦
一鍵三連，好運連連！

你的每一次互動，都是對作者最大的鼓勵！

---

征程尚未結束，讓我們在廣闊的世界里繼續前行！ 🚀