leetcode | Easy | 26. Remove Duplicates from Sorted Array

更新於 發佈於 閱讀時間約 3 分鐘
這個問題「Remove Duplicates from Sorted Array」要求我們從一個已排序的陣列中移除重複的元素,並且返回移除後的陣列新長度。由於陣列已經是排序好的,所以所有的重複元素會是相鄰的。
我們需要移除重複的元素,使每個元素最多只出現一次,並返回去重後的陣列長度。不能使用額外的空間,也就是要「就地」修改原來的陣列。

解法:快慢指針

  1. 設定兩個指針:一個 slow 指針,用來標記不含重複元素的部分;另一個 fast 指針,遍歷整個陣列。
  2. 每當發現 fast 指針指向的元素與 slow 指針指向的元素不相同時,將該元素移動到 slow + 1 的位置,並移動 slow 指針。
  3. fast 指針遍歷到陣列末尾時,slow 指針的值加 1 就是新陣列的長度。

時間複雜度:O(n)

由於我們只需要遍歷一次陣列,因此時間複雜度是 O(n)。

C++程式碼:

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 0; // slow 指針標記不含重複元素的部分

// 例外處理
if (nums.empty()) {
return 0;
}

for (int fast = 1; fast != nums.size(); ++fast) {
if (nums[fast] != nums[slow]) {
++slow;
nums[slow] = nums[fast]; // 移動非重複的元素到 slow + 1 的位置
}
}
return slow + 1; // slow 是索引,所以長度是 slow + 1
}
};

解釋:

  • slow 指針用來標記不含重複元素的部分,fast 指針遍歷整個陣列。
  • 每次 fast 發現不相同的元素時,將該元素移動到 slow + 1 的位置,並將 slow 指針向前移動。
  • 最後 slow + 1 即為新陣列的長度。

以上是 Hua 在 LeetCode 的解題分享,有想法或是建議歡迎在底下討論。
Day Day Good, Day Day Up !


留言
avatar-img
留言分享你的想法!
avatar-img
Hua的沙龍
9會員
8內容數
成功考上研究所,當面對大量的文獻資源時,你可能感到茫然不知如何開始閱讀,也或許不確定該如何開始撰寫畢業論文。在這裡,我將與你分享一些與做研究相關的實用技巧,期望這份指南能夠為初次踏入研究領域的新手帶來實質的協助。
Hua的沙龍的其他內容
2024/11/06
本文介紹了兩種將長度為 n 的陣列元素向右旋轉 k 個位置的方法,分別為使用額外陣列的直觀解法和不使用額外空間的反轉法。本文提供了時間複雜度分析及 C++ 程式碼示例,幫助讀者理解這兩種解法的不同優缺點,並適用於不同情況中的應用。
Thumbnail
2024/11/06
本文介紹了兩種將長度為 n 的陣列元素向右旋轉 k 個位置的方法,分別為使用額外陣列的直觀解法和不使用額外空間的反轉法。本文提供了時間複雜度分析及 C++ 程式碼示例,幫助讀者理解這兩種解法的不同優缺點,並適用於不同情況中的應用。
Thumbnail
2024/11/04
這題是面試中常見的經典題目,要求從一個陣列裡找出出現次數超過一半的元素,也就是所謂的「眾數」。為了更好理解,會先用一個直觀、易懂的方式來解釋問題,透過哈希表的方法來找出答案。接著,我會介紹一個更快、更有效率的解法,也就是 Boyer-Moore 多數投票算法。
Thumbnail
2024/11/04
這題是面試中常見的經典題目,要求從一個陣列裡找出出現次數超過一半的元素,也就是所謂的「眾數」。為了更好理解,會先用一個直觀、易懂的方式來解釋問題,透過哈希表的方法來找出答案。接著,我會介紹一個更快、更有效率的解法,也就是 Boyer-Moore 多數投票算法。
Thumbnail
2024/11/03
今天介紹 LeetCode 「Container With Most Water」,分享兩種解法,包括暴力法和雙指針法。透過 C++ 的逐行解讀,幫助讀者更有效地思考問題,尤其在時間複雜度方面的差異,對於學習演算法與程式設計都有所幫助。
Thumbnail
2024/11/03
今天介紹 LeetCode 「Container With Most Water」,分享兩種解法,包括暴力法和雙指針法。透過 C++ 的逐行解讀,幫助讀者更有效地思考問題,尤其在時間複雜度方面的差異,對於學習演算法與程式設計都有所幫助。
Thumbnail
看更多
你可能也想看
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
題目敘述 Make Two Arrays Equal by Reversing Subarrays 題目給定兩個輸入陣列,請問能否透過子陣列的反轉讓兩個陣列相等? 子陣列的反轉操作次數不受限制。 如果可以,返回True 如果不行,返回False
Thumbnail
題目敘述 Make Two Arrays Equal by Reversing Subarrays 題目給定兩個輸入陣列,請問能否透過子陣列的反轉讓兩個陣列相等? 子陣列的反轉操作次數不受限制。 如果可以,返回True 如果不行,返回False
Thumbnail
題目敘述 Sort Array by Increasing Frequency Leetcode #1636 給定一個輸入陣列,請依照出現頻率的多寡從低頻到高頻排列陣列元素。 如果有兩個元素的出現頻率相同,依照元素大小從大到小排列。 測試範例 Example 1: Input: nums
Thumbnail
題目敘述 Sort Array by Increasing Frequency Leetcode #1636 給定一個輸入陣列,請依照出現頻率的多寡從低頻到高頻排列陣列元素。 如果有兩個元素的出現頻率相同,依照元素大小從大到小排列。 測試範例 Example 1: Input: nums
Thumbnail
題目敘述 Intersection of Two Arrays II 給定兩個輸入陣列,請找出兩個陣列交集的元素,並且依照出現次數輸出。 測試範例 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] 交集元素
Thumbnail
題目敘述 Intersection of Two Arrays II 給定兩個輸入陣列,請找出兩個陣列交集的元素,並且依照出現次數輸出。 測試範例 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] 交集元素
Thumbnail
給定一個字串陣列,請把它們所共有的字元伴隨著出現次數輸出。這篇文章介紹如何使用字典統計出現次數,和字典取交集的方法來解決此問題。並提供了複雜度分析和關鍵知識點。
Thumbnail
給定一個字串陣列,請把它們所共有的字元伴隨著出現次數輸出。這篇文章介紹如何使用字典統計出現次數,和字典取交集的方法來解決此問題。並提供了複雜度分析和關鍵知識點。
Thumbnail
題目敘述 題目會給定一個整數陣列nums,原本裡面包含有整數1到n,但是中間不小心出了差錯,導致有一個數字消失了,而另一個數字重複了。 請找出重複的數字以及消失的數字,並且 以陣列的形式[重複的數字, 消失的數字]返回這兩個數字。 例如: [1,3,3,4] 消失的數字是2,重複的數字是
Thumbnail
題目敘述 題目會給定一個整數陣列nums,原本裡面包含有整數1到n,但是中間不小心出了差錯,導致有一個數字消失了,而另一個數字重複了。 請找出重複的數字以及消失的數字,並且 以陣列的形式[重複的數字, 消失的數字]返回這兩個數字。 例如: [1,3,3,4] 消失的數字是2,重複的數字是
Thumbnail
題目敘述 題目會給定一個整數陣列arr,要求我們判斷是否每個元素的出現次數都不同? 題目的原文敘述 測試範例 Example 1: Input: arr = [1,2,2,1,1,3] Output: true Explanation: The value 1 has 3 occurre
Thumbnail
題目敘述 題目會給定一個整數陣列arr,要求我們判斷是否每個元素的出現次數都不同? 題目的原文敘述 測試範例 Example 1: Input: arr = [1,2,2,1,1,3] Output: true Explanation: The value 1 has 3 occurre
Thumbnail
題目 : 83. Remove Duplicates from Sorted List
Thumbnail
題目 : 83. Remove Duplicates from Sorted List
Thumbnail
題目 : 27. Remove Element
Thumbnail
題目 : 27. Remove Element
Thumbnail
題目 : 88. Merge Sorted Array
Thumbnail
題目 : 88. Merge Sorted Array
Thumbnail
題目敘述 題目會給我們一個整數陣列,裡面包含各種正整數,每回合可以消去兩個相同的數字,或者消去三個相同的數字。問最少需要幾次消去,才能讓陣列為空? 如果無解,則返回-1 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [2,3,3,2,2,4,2,3,
Thumbnail
題目敘述 題目會給我們一個整數陣列,裡面包含各種正整數,每回合可以消去兩個相同的數字,或者消去三個相同的數字。問最少需要幾次消去,才能讓陣列為空? 如果無解,則返回-1 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [2,3,3,2,2,4,2,3,
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News