一、問題

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

要求：

1. 原地修改： 必須直接修改輸入數(shù)組 nums。不允許使用額外的空間。
2. 相對順序： 元素之間的相對順序必須保持一致。
3. 返回唯一元素個數(shù)： 返回?cái)?shù)組中唯一元素的個數(shù) k。
4. 數(shù)組內(nèi)容： 數(shù)組 nums 的前 k 個元素應(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)該返回新的長度 k = 5, 并且 nums 的前五個元素為 0, 1, 2, 3, 4。 不需要考慮數(shù)組中超出新長度后面的元素。

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

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

二、問題分析

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

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

解題思路： 由于數(shù)組已排序，可以使用雙指針方法來解決這個問題。雙指針方法通常用于原地操作，且效率較高。

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

算法步驟：

1. 初始化：
   • i = 0 （慢指針，指向數(shù)組的第一個位置，即第一個唯一元素應(yīng)該放置的位置）。
   • j = 1 （快指針，從數(shù)組的第二個位置開始遍歷）。
2. 遍歷數(shù)組：
   • 使用 j 遍歷數(shù)組 nums。
   • 如果 nums[j] != nums[i]： 說明 nums[j] 是一個新的唯一元素。
     • 將 i 向前移動一位（i++）。
     • 將 nums[j] 復(fù)制到 nums[i] 的位置（nums[i] = nums[j]）。
   • 否則 (如果 nums[j] == nums[i])： 說明 nums[j] 是一個重復(fù)元素，跳過它。
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ù)雜度分析：

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

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

由于數(shù)組已排序，可以使用雙指針方法來解決這個問題。

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;
    }
};

四、問題變體：最多保留兩次

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

要求：

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

示例：

輸入：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,_]

說明：

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

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

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

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

5.1、問題分析

可以將問題分解為以下幾個子問題：

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

算法思路： 基于雙指針方法，結(jié)合計(jì)數(shù)器來解決此問題。

• 慢指針（i）： 指向下一個要保留的元素應(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： 說明當(dāng)前元素允許被保留。
       • 將 nums[j] 復(fù)制到 nums[i] 的位置 ( nums[i] = nums[j] )。
       • i++ (移動慢指針)。
   • 情況 2：nums[j] != nums[j-1] (遇到不同元素)
     • nums[i] = nums[j]
     • i++
     • count=1

3. 返回結(jié)果： 循環(huán)結(jié)束后，i 就是數(shù)組中應(yīng)該保留的元素個數(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ù)雜度分析：

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

5.3、快慢指針（推薦）

原理：

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

示例演示： 假設(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; // 少于等于兩個元素，直接返回
        }

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

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

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

復(fù)雜度分析：

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

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

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

思路是正確的，但存在一些效率問題和潛在的錯誤。核心問題在于，對于每個需要刪除的元素，都進(jìn)行一次循環(huán)移動操作，這會導(dǎo)致時間復(fù)雜度過高，尤其是在重復(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é)

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

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

最新評論