Leetcode 26. 移除已排序陣列中的重複項

題目

一樣不免俗地，先看題目。

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.

題目說，給定一個從非遞減的已排序整數陣列（白話：遞增 int[]），用原地演算法（In-Place）移除重複項，直到每一個元素只會出現一個。

測資

測資一

+ Input: nums = [1,1,2]
+ Output: 2, nums = [1,2,_]
- Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
- It does not matter what you leave beyond the returned k (hence they are underscores).

測資二

+ Input: nums = [0,0,1,1,1,2,2,3,3,4]
+ Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
- Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
- It does not matter what you leave beyond the returned k (hence they are underscores).

其實測資不難懂，輸入的是 int[] 遞增陣列，然後輸出整數，而這個整數是已經排序好的最後一個值。舉例來說，當輸入 [0,0,1,1,1,2,2,3,3,4]，去重後會得到 [0,1,2,3,4]，但因為題目說要採用原地演算法，因此陣列大小是不會改變的，所以會變成 [0,1,2,3,4,XXX,XXX,XXX,XXX,XXX]，接著只要 return 5，就知道是前五個元素，即可。

第一種寫法（暴力解）

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;   // 邏輯上的有效長度
        int i = 1;

        while (i < len) {
            if (nums[i] == nums[i - 1]) {
                // 把 i 後面的元素全部往前挪一格，蓋掉 nums[i]
                for (int j = i; j < len - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                len--;          // 有效長度少 1
                // i 不動，因為新搬過來的值還沒檢查
            } else {
                i++;
            }
        }
        return len;
    }
}

思路

一開始的想法是，遍歷所有元素，先把 nums[i] 和 nums[i-1] 做比對，如果是相等，則再寫一個迴圈去把後面的值往前推。

雖然這樣做蠻好理解的，但是很顯然完全沒效率，等於用了兩層迴圈去解。

時間複雜度: O(n^2) 空間複雜度: O(1)

第二種寫法（雙指標解）

class Solution {
    public int removeDuplicates(int[] nums) {
        // 基準值
        int k = -101;

        // 存位置
        int position = 0;

        for (int i = 1; i < nums.length; i++){
            if (i == 1)
                k = nums[0];

            if (k == nums[i])
                continue;
            else {
                k = nums[i];
                position += 1;
                nums[position] = k;
            }
        }

        return position + 1;
    }
}

思路

1. 我先存一個基準值 k 當作基準比對對象，往後的值都和 k 去做比對。
2. 宣告一個變數為 position，是存新的 k 值，該存放在哪一個 index。
3. 先將 nums[0] 放入 k 中，開始遍歷 i=1~nums.length，如果 k 與 nums[i] 相同，則跳過；如果不同，則將 nums[i] 放入 k，且將 position + 1，再將 k 賦值於 nums[position]。因為 nums 本來就已經排序了，固然依 position 放入 nums 時，也會排序好。
4. 此時會得到 $[p_1, p_2, \dots, p_n, v_1, v_2, \dots, v_n]$，則只需要將 position+1 返回即可。會加 1 是因為一開始 position 是從 index = 0 開始跑，因此要加一返回。

過程

初始: 先將 k = nums[0] = 0，position = 0。

i = 1:

$[ \underset{\underset{p}{k}}{\mathstrut 0}, \underset{\triangle}{0}, 1, 1, 1, 2, 2, 3, 3, 4 ]$

k=0 與 nums[1] 比對，發現 0 == 0，則跳過，position 維持 0。

i = 2:

$[ 0, \underset{\underset{p}{k}}{\mathstrut 1}, \underset{\triangle}{1}, 1, 1, 2, 2, 3, 3, 4 ]$

k=0 與 nums[2] 比對，發現 1 != 0，position += 1 變成 1，將 1 放入 k，並執行 nums[1] = 1。

i = 3:

$[ 0, \underset{\underset{p}{k}}{\mathstrut 1}, 1, \underset{\triangle}{1}, 1, 2, 2, 3, 3, 4 ]$

k=1 與 nums[3] 比對，發現 1 == 1，則跳過，position 維持 1。

i = 4:

$[ 0, \underset{\underset{p}{k}}{\mathstrut 1}, 1, 1, \underset{\triangle}{1}, 2, 2, 3, 3, 4 ]$

k=1 與 nums[4] 比對，發現 1 == 1，則跳過，position 維持 1。

i = 5:

$[ 0, 1, \underset{\underset{p}{k}}{\mathstrut 2}, 1, 1, \underset{\triangle}{2}, 2, 3, 3, 4 ]$

k=1 與 nums[5] 比對，發現 2 != 1，position += 1 變成 2，將 2 放入 k，並執行 nums[2] = 2。

i = 6:

$[ 0, 1, \underset{\underset{p}{k}}{\mathstrut 2}, 1, 1, 2, \underset{\triangle}{2}, 3, 3, 4 ]$

k=2 與 nums[6] 比對，發現 2 == 2，則跳過，position 維持 2。

i = 7:

$[ 0, 1, 2, \underset{\underset{p}{k}}{\mathstrut 3}, 1, 2, 2, \underset{\triangle}{3}, 3, 4 ]$

k=2 與 nums[7] 比對，發現 3 != 2，position += 1 變成 3，將 3 放入 k，並執行 nums[3] = 3。

i = 8:

$[ 0, 1, 2, \underset{\underset{p}{k}}{\mathstrut 3}, 1, 2, 2, 3, \underset{\triangle}{3}, 4 ]$

k=3 與 nums[8] 比對，發現 3 == 3，則跳過，position 維持 3。

i = 9:

$[ 0, 1, 2, 3, \underset{\underset{p}{k}}{\mathstrut 4}, 2, 2, 3, 3, \underset{\triangle}{4} ]$

k=3 與 nums[9] 比對，發現 4 != 3，position += 1 變成 4，將 4 放入 k，並執行 nums[4] = 4。

結束:

$[ \underbrace{0, 1, 2, 3, 4}_{\text{要的區域}}, 2, 2, 3, 3, 4 ]$

迴圈結束，position = 4，回傳 position + 1 = 5，代表前 5 個元素 [0, 1, 2, 3, 4]。

時間複雜度: O(n) 空間複雜度: O(1)

提交結果

相關文章

《Leetcode 27. 移除陣列中的指定元素》

《Leetcode 1768. 交替合併字串》