26. Remove Duplicates from Sorted Array

難度: Easy

類型: Array, Two Pointers

CPP程式下載: 26.cpp

前情題要:

給一個從小到大排序的陣列, 要求把重複地剔除, 並回傳unique數的個數, 以及剔除重複值後的陣列。

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.

Consider the number of unique elements in nums to be k​​​​​​​​​​​​​​. After removing duplicates, return the number of unique elements k.

The first k elements of nums should contain the unique numbers in sorted order. The remaining elements beyond index k - 1 can be ignored.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

 

Example 1:

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).

Example 2:

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).

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

思考方式:

1. 其實不必兩個 pointer, 兩個 index 就可以了, 一樣意思。

2. 重複的剔掉後, 後面 array 的值為 don't case, 不必處理。

複雜度思考:

Time Complexity: Worst case: O( N )

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 22.66 MB, Beats: 50.08%

Accepted

362 / 362 testcases passed

tendchen

submitted at Nov 10, 2025 20:44

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

22.66MB

Beats50.08%

Analyze Complexity

Code

C++

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int iSize = nums.size();
        int iUniqueNum=1;
        //int iPreNum;
        int iInputIndex=1;
        int iOutptIndex=1;
        for (;iInputIndex<iSize;iInputIndex++)
        {
            if (nums.at(iInputIndex)==nums.at(iInputIndex-1))
            {
                continue;
            }
            else
            {
                nums.at(iOutptIndex)=nums.at(iInputIndex);
                //cout << "iInputIndex=" << iInputIndex << "\n";
                //cout << "iOutptIndex=" << iOutptIndex << "\n";
                iOutptIndex++;
            }
        }
        //while (++iOutptIndex<iSize)
        //{
        //    nums.at(iOutptIndex)=
        //}
        return iOutptIndex;
    }
};