一、問(wèn)題

給定一個(gè)非嚴(yán)格遞增排序的整數(shù)數(shù)組 nums，請(qǐng)、原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次。返回刪除后數(shù)組的新長(zhǎng)度。

要求：

1. 原地修改： 必須直接修改輸入數(shù)組 nums。不允許使用額外的空間。
2. 相對(duì)順序： 元素之間的相對(duì)順序必須保持一致。
3. 返回唯一元素個(gè)數(shù)： 返回?cái)?shù)組中唯一元素的個(gè)數(shù) k。
4. 數(shù)組內(nèi)容： 數(shù)組 nums 的前 k 個(gè)元素應(yīng)包含唯一元素，并且按照它們最初在 nums 中出現(xiàn)的順序排列。 nums 數(shù)組中下標(biāo) k 及之后的部分的內(nèi)容可以任意修改，其值不影響結(jié)果。

示例：

輸入：nums = [1,1,2]
輸出：2, nums = [1,2,_] // 下劃線表示不重要的位置

輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4,,,,,_]

解釋：

函數(shù)應(yīng)該返回新的長(zhǎng)度 k = 5, 并且 nums 的前五個(gè)元素為 0, 1, 2, 3, 4。 不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

關(guān)鍵點(diǎn)：

• 非嚴(yán)格遞增： 意味著數(shù)組是排序的，但不一定是嚴(yán)格升序 (允許重復(fù)元素)。
• 原地刪除： 空間復(fù)雜度必須是 O(1)。
• 相對(duì)順序不變： 刪除重復(fù)元素后，剩余元素的順序要與原始數(shù)組中的順序相同。

二、問(wèn)題分析

核心目標(biāo)： 從已排序的數(shù)組中移除重復(fù)元素，確保每個(gè)唯一元素只出現(xiàn)一次，并返回唯一元素的數(shù)量。
約束條件：

• 原地操作： 這是最關(guān)鍵的約束。我們不能創(chuàng)建新的數(shù)組來(lái)存儲(chǔ)結(jié)果。必須直接修改原始數(shù)組。
• 相對(duì)順序： 刪除重復(fù)項(xiàng)后，唯一元素的相對(duì)順序必須與原始數(shù)組保持一致。
• 排序特性： 輸入數(shù)組是已排序的。這是一個(gè)重要的前提，允許我們使用更高效的算法。

解題思路： 由于數(shù)組已排序，可以使用雙指針?lè)椒▉?lái)解決這個(gè)問(wèn)題。雙指針?lè)椒ㄍǔＳ糜谠夭僮鳎倚瘦^高。

• 慢指針（i）： 指向下一個(gè)非重復(fù)元素應(yīng)該放置的位置。
• 快指針（j）： 用于遍歷數(shù)組，查找非重復(fù)元素。

算法步驟：

1. 初始化：
   • i = 0 （慢指針，指向數(shù)組的第一個(gè)位置，即第一個(gè)唯一元素應(yīng)該放置的位置）。
   • j = 1 （快指針，從數(shù)組的第二個(gè)位置開始遍歷）。
2. 遍歷數(shù)組：
   • 使用 j 遍歷數(shù)組 nums。
   • 如果 nums[j] != nums[i]： 說(shuō)明 nums[j] 是一個(gè)新的唯一元素。
     • 將 i 向前移動(dòng)一位（i++）。
     • 將 nums[j] 復(fù)制到 nums[i] 的位置（nums[i] = nums[j]）。
   • 否則 (如果 nums[j] == nums[i])： 說(shuō)明 nums[j] 是一個(gè)重復(fù)元素，跳過(guò)它。
3. 返回結(jié)果： 循環(huán)結(jié)束后，i + 1 就是數(shù)組中唯一元素的數(shù)量（因?yàn)?nbsp;i 是索引，從 0 開始）。

示例演示： 假設(shè) nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

最終結(jié)果：nums = [0, 1, 2, 3, 4, ...]，返回 i + 1 = 5

復(fù)雜度分析：

• 時(shí)間復(fù)雜度： O(n)，其中 n 是數(shù)組的長(zhǎng)度。我們需要遍歷數(shù)組一次。
• 空間復(fù)雜度： O(1)，原地操作，只使用了常數(shù)級(jí)別的額外空間。

三、算法實(shí)現(xiàn)

由于數(shù)組已排序，可以使用雙指針?lè)椒▉?lái)解決這個(gè)問(wèn)題。

1. 初始化快慢指針。
2. 遍歷數(shù)組。
3. 返回結(jié)果。

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

四、問(wèn)題變體：最多保留兩次

刪除有序數(shù)組中的多余重復(fù)項(xiàng) (最多保留兩次)： 給定一個(gè)已排序的數(shù)組 nums，請(qǐng) 原地 刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素最多出現(xiàn)兩次。返回刪除后數(shù)組的新長(zhǎng)度。

要求：

1. 原地修改： 必須直接修改輸入數(shù)組 nums。不允許使用額外的數(shù)組空間。
2. O(1) 額外空間： 必須在 O(1) 的額外空間復(fù)雜度下完成此操作。
3. 相對(duì)順序： 元素的相對(duì)順序必須保持一致。
4. 返回值： 返回刪除重復(fù)元素后的數(shù)組的新長(zhǎng)度 k。
5. 數(shù)組內(nèi)容： 數(shù)組 nums 的前 k 個(gè)元素應(yīng)該包含處理后的元素，超出 k 長(zhǎng)度的部分可以忽略。

示例：

輸入：nums = [1,1,1,2,2,3]
輸出：5, nums = [1,1,2,2,3,_] // 下劃線表示不重要的位置

輸入：nums = [0,0,0,1,1,1,2,2,3,3,4]
輸出：9, nums = [0,0,1,1,2,2,3,3,4,_]

說(shuō)明：

• 對(duì)于 nums = [1,1,1,2,2,3]，函數(shù)應(yīng)該返回新的長(zhǎng)度 k = 5，并且 nums 的前五個(gè)元素為 1, 1, 2, 2, 3。
• 對(duì)于 nums = [0,0,0,1,1,1,2,2,3,3,4]，函數(shù)應(yīng)該返回新的長(zhǎng)度 k = 9，并且 nums 的前九個(gè)元素為 0, 0, 1, 1, 2, 2, 3, 3, 4。

關(guān)鍵點(diǎn)：

• 有序數(shù)組： 輸入數(shù)組是已排序的，利用這一特性可以優(yōu)化算法。
• 最多保留兩次： 每個(gè)元素最多允許出現(xiàn)兩次。
• 原地修改 + O(1)： 限制了算法的選擇，必須采用空間復(fù)雜度為常數(shù)的算法。

五、分析和代碼實(shí)現(xiàn)

5.1、問(wèn)題分析

可以將問(wèn)題分解為以下幾個(gè)子問(wèn)題：

• 識(shí)別重復(fù)項(xiàng)： 如何有效地識(shí)別重復(fù)出現(xiàn)的元素？ 由于數(shù)組是有序的，相鄰元素相同則為重復(fù)。
• 計(jì)數(shù)： 如何記錄每個(gè)元素出現(xiàn)的次數(shù)？ 需要一個(gè)變量來(lái)追蹤當(dāng)前元素出現(xiàn)的次數(shù)。
• 原地修改： 如何在不使用額外空間的情況下，將需要保留的元素移動(dòng)到數(shù)組的前面？ 使用雙指針?lè)椒ㄊ顷P(guān)鍵。
• 更新長(zhǎng)度： 如何計(jì)算并返回修改后的數(shù)組長(zhǎng)度？ 慢指針的最終位置 + 1 就是新長(zhǎng)度。

算法思路： 基于雙指針?lè)椒ǎY(jié)合計(jì)數(shù)器來(lái)解決此問(wèn)題。

• 慢指針（i）： 指向下一個(gè)要保留的元素應(yīng)該放置的位置。
• 快指針（j）： 用于遍歷數(shù)組，檢查元素是否應(yīng)該被保留。
• 計(jì)數(shù)器（count）： 記錄當(dāng)前元素連續(xù)出現(xiàn)的次數(shù)。

5.2、算法實(shí)現(xiàn)

算法步驟：

1. 初始化：

   • i = 0 (慢指針)
   • j = 0 (快指針)
   • count = 1 (初始計(jì)數(shù)為 1，因?yàn)?nbsp;nums[0] 至少出現(xiàn)一次)

2. 遍歷數(shù)組：

   • 循環(huán) j 從 1 到 nums.length - 1。
   • 情況 1：nums[j] == nums[j-1] (遇到相同元素)
     • count++ (增加計(jì)數(shù)器)。
     • 如果 count <= 2： 說(shuō)明當(dāng)前元素允許被保留。
       • 將 nums[j] 復(fù)制到 nums[i] 的位置 ( nums[i] = nums[j] )。
       • i++ (移動(dòng)慢指針)。
   • 情況 2：nums[j] != nums[j-1] (遇到不同元素)
     • nums[i] = nums[j]
     • i++
     • count=1

3. 返回結(jié)果： 循環(huán)結(jié)束后，i 就是數(shù)組中應(yīng)該保留的元素個(gè)數(shù)，因此返回 i。

示例演示： 假設(shè) nums = [1,1,1,2,2,3]

最終結(jié)果：nums = [1, 1, 2, 2, 3, ...]，返回 i = 5

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n < 3)
            return n;
        int left = 1;
        int count = 1;
        for (int right = 1; right < n; ++right) {
            if (nums[right - 1] == nums[right]) {
                ++count;
                if (count <= 2) {
                    nums[left] = nums[right];
                    ++left;
                }
            } else {
                nums[left] = nums[right];
                ++left;
                count = 1;
            }
        }
        return  left;
    }
};

復(fù)雜度分析：

• 時(shí)間復(fù)雜度： O(n)，其中 n 是數(shù)組的長(zhǎng)度。需要遍歷數(shù)組一次。
• 空間復(fù)雜度： O(1)，使用了常數(shù)級(jí)別的額外空間（i, j, count）。

5.3、快慢指針（推薦）

原理：

• slow 指針初始值為 2，因?yàn)樗硎拘聰?shù)組中前兩個(gè)元素已經(jīng)確定（即原數(shù)組的前兩個(gè)元素）。
• fast 指針從 2 開始遍歷數(shù)組。
• 如果 nums[fast] 與 nums[slow - 2] 不相等，則說(shuō)明 nums[fast] 可以被添加到新數(shù)組中，將其賦值給 nums[slow]，并同時(shí)遞增 slow 指針。
• 如果 nums[fast] 與 nums[slow - 2] 相等，則說(shuō)明 nums[fast] 是多余的重復(fù)元素，直接跳過(guò)。
• 循環(huán)結(jié)束后，slow 指針的值就是新數(shù)組的長(zhǎng)度。

示例演示： 假設(shè) nums = [1,1,1,2,2,3]

最終結(jié)果：nums = [1, 1, 2, 2, 3, ...]，返回 slow = 5

代碼實(shí)現(xiàn)：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) {
            return n; // 少于等于兩個(gè)元素，直接返回
        }

        int slow = 2; // slow指針指向下一個(gè)要放置的位置，從第三個(gè)位置開始
        int fast = 2; // fast指針用于遍歷數(shù)組

        while (fast < n) {
            // 如果當(dāng)前元素與slow指針的前兩個(gè)元素不同，說(shuō)明可以保留
            if (nums[fast] != nums[slow - 2]) {
                nums[slow] = nums[fast]; // 將fast指針指向的元素移動(dòng)到slow指針的位置
                slow++; // slow指針向后移動(dòng)
            }
            fast++; // fast指針始終向后移動(dòng)
        }

        return slow; // slow指針的值就是新數(shù)組的長(zhǎng)度
    }
};

復(fù)雜度分析：

• 時(shí)間復(fù)雜度： O(n)，其中 n 是數(shù)組的長(zhǎng)度。只需要遍歷數(shù)組一次。
• 空間復(fù)雜度： O(1)，使用了常數(shù)級(jí)別的額外空間（slow, fast）。

5.4、低效率的代碼實(shí)現(xiàn)

思路：對(duì)于超過(guò) 2 次的重復(fù)元素，超出部分使用循環(huán)將它們移動(dòng)到數(shù)組的末尾。

思路是正確的，但存在一些效率問(wèn)題和潛在的錯(cuò)誤。核心問(wèn)題在于，對(duì)于每個(gè)需要?jiǎng)h除的元素，都進(jìn)行一次循環(huán)移動(dòng)操作，這會(huì)導(dǎo)致時(shí)間復(fù)雜度過(guò)高，尤其是在重復(fù)元素較多的情況下。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n < 3)
            return n;
        int left = 0;
        for (int right = 1; right < n; ++right) {
            if (nums[left] != nums[right]) {
                left = right;
                continue;
            }
            if (right - left > 1) {
                for (int i = right - 1; i < (n - 1); ++i) 
                    std::swap(nums[i], nums[i + 1]);
                --n;
                --right;
            }
        }
        return n;
    }
};

六、總結(jié)

雙指針?lè)椒ㄊ且粋€(gè)解決此類原地修改問(wèn)題的有效方法。通過(guò)維護(hù)兩個(gè)指針，一個(gè)指向下一個(gè)唯一元素的位置，另一個(gè)用于遍歷數(shù)組，我們可以高效地刪除重復(fù)項(xiàng)并保持相對(duì)順序不變。 理解排序數(shù)組的特性對(duì)于選擇正確的算法至關(guān)重要。

以上就是C++原地刪除有序數(shù)組重復(fù)項(xiàng)的N種方法的詳細(xì)內(nèi)容，更多關(guān)于C++刪除有序數(shù)組重復(fù)項(xiàng)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論