1. 題目

1.1 英文題目

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-placein-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.

1.2 中文題目

給你一個有序陣列 nums ，請你 原地 洗掉重復出現的元素，使每個元素 只出現一次 ，回傳洗掉后陣列的新長度，不要使用額外的陣列空間，你必須在 原地 修改輸入陣列 并在使用 O(1) 額外空間的條件下完成，

1.3輸入輸出

| 輸入 | 輸出 |
| nums = [1,1,2] | 2, nums = [1,2,_] |

| [0,0,1,1,1,2,2,3,3,4] | 5, nums = [0,1,2,3,4,,,,,_] |

2. 實驗平臺

IDE：VS2019
IDE版本：16.10.1
語言：c++11

3. 程式

3.1 測驗程式

#include "Solution.h"
#include <vector>  // std::vector
#include<iostream> // std::cout
using namespace std;

// 主程式
void main()
{
vector<int> nums = { 0,0,0,1,1,1,2,2,3,4,4 }; // 輸入
Solution solution; // 實體化Solution
int k = solution.removeDuplicates(nums); // 主功能

// 輸出
cout << k << ", [";
for (int i = 0; i < k; i++)
{
if (i == k - 1)
cout << nums[i] << "]";
else
cout << nums[i] << ",";
}
}

3.2 功能程式

3.2.1 最佳程式

（1）代碼

#pragma once
#include<vector>    // std::vector
using namespace std;

//主功能
class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        if (nums.size() > 1)
        {
            int i; // i為慢指標，指向的是去重后最后一位，隨j更新
            int j; // j為快指標，不斷向前探索
            for (i = 0, j = 0; j < nums.size(); j++)
            {
                if (nums[i] != nums[j])  // 若快指標所指元素與慢指標相同，則慢的不動，快的前進一步
                    nums[++i] = nums[j]; // 若不同，則慢的前進一步指向快指標指的元素，快指標繼續向前一步
            }
            return i + 1; // 因為下標從0開始，所以去重后的元素個數為i+1
        }
    }
};

此程式參考：https://blog.csdn.net/qjh5606/article/details/81434396

（2）解讀

快慢指標，慢的指向的一直都是新的，也就是說來一個新的它才往前走一步，快的就是不斷向前，發現和慢的不一樣的就匯報給那個慢的，然后慢的更新，如果二者相等，則慢的不動，快的前進一步；如果二者不等，則慢的前進一步的同時更新那個新一步指向的數字為現在快指標指向的新數字，快的同時也往前走一步，

解讀參考：https://www.cnblogs.com/forPrometheus-jun/p/10889152.html

3.2.2 自寫程式

（1）代碼

#pragma once
#include<vector>    // std::vector
#include<algorithm> // std::find
using namespace std;

//主功能
class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        if (nums.size() > 1) // 若nums不是空集合或單元素集合
        {
            int i = 1;
            while (i != nums.size())
            {
                if (nums[i] == nums[i - 1]) // 若元素重復
                    nums.erase(find(nums.begin(), nums.end(), nums[i])); //則去除重復數字
                else // 若元素不重復
                    i += 1; // 則向后再查看一個元素
            }
        }
        return nums.size(); // 回傳結果
    }
};

（2）思路

從前往后遍歷，如果發現有元素重復，則將重復元素剔除

3.2.3 其他程式

（1）代碼

#pragma once
#include<vector>    // std::vector
#include<algorithm> // std::unique
using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
        return nums.size();
    }
};

（2）解讀

該程式直接使用 c++標準模板庫STL中的函式std::unique查找重復元素，更簡潔，

4. 相關知識

（1） 快慢指標（Fast-Slow Pointer）

這幾個教程挺不錯的，可以參考一下：
https://www.cnblogs.com/hxsyl/p/4395794.html
https://blog.csdn.net/SoftPoeter/article/details/103153564
https://zhuanlan.zhihu.com/p/361049436

（2） i++與++i的區別

• i++ 即后加加，原理是：先自增，然后回傳自增之前的值
• ++i 即前加加，原理是：先自增，然后回傳自增之后的值

參考：https://blog.csdn.net/android_cai_niao/article/details/106027313

標籤：C++

上一篇：65.QT-UDP組播實作多人共享桌面(同時支持收發顯示)

下一篇：深入理解 sync.Once 與 sync.Pool