LeetCode #26 Remove Duplicates from Sorted Array 已排列陣列移除重複元素

LeetCode題目翻譯

英文原文如下

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

中文翻譯

給予一個非遞減排序的 陣列 nums, 原地移除重複的元素，讓每個元素只出現一次。元素間相對的順序要保持相同。

由於某些語言改變陣列的長度是不可能的，所以你必須將結果放在 nums 的前段部分。更正式來說，如果移除後的結果有 k 個元素，那 nums 的前 k 個元素就該是最終的答案。超過 k 個元素的部分可以被省略。

再將結果放在前 k 個元素之後，回傳 k。

不要分配空間給另一個陣列，你必須要更改原先輸入陣列並使用 O(1) 的額外空間來完成。

⭐真的不是我要講，這題的英文真的烙烙長…

(反正就是要把陣列剃除重複元素，並回傳剩餘的數量這樣)

範例及題目限制

這題比較特殊一點，附上了驗證的過程會如何進行

反正就是會用你的 nums陣列的前 k 個元素跟正確答案相對位置進行比較

解題思路

需要記住的只有一點，要返回整數 k 以及變更 nums 陣列

C# 解決方案

方案1

public class Solution {
    public int RemoveDuplicates(int[] nums) {
      
        int tmp = nums[0];
        int cnt = 1;
        
        for(int i = 1;i<nums.Length;i++)
        {
            if(nums[i]>tmp)
            {
                tmp = nums[i];
                nums[cnt] = tmp;
                cnt++;
            }
        }
        
        return cnt;
    }
}

用來判斷的方法也非常簡單呢，需要兩個變數 tmp 跟 cnt

一個表示當前最大值，一個表示當前更改到的索引

索引從 1 開始，是因為要將第一個元素當作 tmp 的初始值

判斷的時候，就是判斷當前更改到的所引的值是否大於 tmp

若是的話則更新 nums[cnt] 的值，並更新為新的 tmp 值 ( ➡能這樣判斷是因為題目敘述中的非遞減式排序)

Java解決方案

方案1

class Solution {
    public int removeDuplicates(int[] nums) {
        int tmp = nums[0];
        int cnt = 1;
        
        for(int i = 1;i<nums.length;i++)
        {
            if(nums[i]>tmp)
            {
                tmp = nums[i];
                nums[cnt] = tmp;
                cnt++;
            }
        }
        
        return cnt;
    }
}

Python3 解決方案

方案1

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        tmp = nums[0]
        cnt = 1
        
        for i in range (1,len(nums)):
            if nums[i]>tmp :
                tmp = nums[i]
                nums[cnt] = tmp
                cnt+=1
                
        return cnt

JavaScript 解決方案

方案1

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    var tmp = nums[0];
    var cnt = 1;

    for(var i = 1;i<nums.length;i++)
    {
        if(nums[i]>tmp)
        {
            tmp = nums[i];
            nums[cnt] = tmp;
            cnt++;
        }
    }
    return cnt;
};

結論

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡可以的話，幫我點個小小的廣告，我會很感謝的 (每天吃土來付主機費ing)

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Remove Duplicates from Sorted Array – LeetCode

這裡看下一題 : LeetCode #27 Remove Element 移除元素 – Zyrastory-當程式碰上美食

隨機文章