N methods for deleting ordered array duplicates in place in C++

1. Problem

Given an array of integers that are not strictly incrementally sortednums,please,In placeDelete duplicate elements so that each element isOnly appear once. Returns the new length of the array after deletion.

Require:

1. Modified in place:The input array must be modified directly.nums. No extra space is allowed.
2. Relative order:The relative order between elements must be consistent.
3. Returns the number of unique elements:Returns the number of unique elements in the arrayk。
4. Array content:ArraynumsThe frontkElements should contain unique elements and as they were originally innumsThe order in which it appears.numsSubscript in arraykThe contents of the subsequent parts can be modified arbitrarily, and their value will not affect the result.

Example:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_] // Underscore indicates unimportant position

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]

explain:

The function should return a new lengthk = 5, andnumsThe first five elements are0, 1, 2, 3, 4. No need to consider elements in the array beyond the new length.

Key points:

• Non-strict increment:Meaning that the array is sorted, but not necessarily in strict ascending order (repeated elements are allowed).
• Delete in place:The space complexity must be O(1).
• The relative order remains unchanged:After deleting duplicate elements, the order of the remaining elements must be the same as in the original array.

2. Problem analysis

Core Objectives:Remove duplicate elements from the sorted array, making sure each unique element only appears once, and returns the number of unique elements.
Constraints:

• Operation in place:This is the most critical constraint. We cannot create new arrays to store results. The original array must be modified directly.
• Relative order:After deleting duplicates, the relative order of the unique elements must be consistent with the original array.
• Sorting features:The input array is sorted. This is an important premise that allows us to use more efficient algorithms.

Problem solution:Since the array is sorted, you can use the double pointer method to solve this problem. The double pointer method is usually used for in-situ operation and is efficient.

• Slow pointer (i）：Point to where the next non-repeat element should be placed.
• Fast pointer (j）：Used to traverse arrays and find non-repetitive elements.

Algorithm steps:

1. initialization:
   • i = 0(Slow pointer, pointing to the first position of the array, i.e. where the first unique element should be placed).
   • j = 1(Fast pointer, traversal from the second position of the array).
2. Iterate over the array:
   • usejTransfer the arraynums。
   • ifnums[j] != nums[i]：illustratenums[j]is a new only element.
     • WilliMove one forward (i++）。
     • Willnums[j]Copy tonums[i]Location (nums[i] = nums[j]）。
   • Otherwise (ifnums[j] == nums[i])：illustratenums[j]is a repeating element, skip it.
3. Return result:After the cycle ends,i + 1It is the number of unique elements in the array (becauseiis the index, starting from 0).

Sample demonstration:Assumptionnums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

Final result:nums = [0, 1, 2, 3, 4, ...],returni + 1 = 5

Complexity analysis:

• Time complexity:O(n), where n is the length of the array. We need to iterate over the array once.
• Space complexity:O(1), operates in place, only use additional space at the constant level.

III. Algorithm implementation

Since the array is sorted, you can use the double pointer method to solve this problem.

1. Initialize the fast and slow pointer。
2. Iterate through the array。
3. Return result。

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

4. Problem variant: keep it twice at most

Delete redundant duplicates in an ordered array (maximum two retained):Given a sorted arraynums,pleaseIn placeDelete the repeated elements so that each element appears at most twice. Returns the new length of the array after deletion.

Require:

1. Modified in place:The input array must be modified directly.nums. No additional array space is allowed.
2. O(1) Extra space:This must be done with the extra space complexity of O(1).
3. Relative order:The relative order of elements must be consistent.
4. Return value:Returns the new length of the array after deleting the duplicate elementsk。
5. Array content:ArraynumsThe frontkElements should contain processed elements, exceedingkThe length part can be ignored.

Example:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_] // Underscore indicates unimportant position

Input: nums = [0,0,0,1,1,1,2,2,3,3,4]
Output: 9, nums = [0,0,1,1,2,2,3,3,4,_]

illustrate:

• Fornums = [1,1,1,2,2,3], the function should return the new lengthk = 5, andnumsThe first five elements are1, 1, 2, 2, 3。
• Fornums = [0,0,0,1,1,1,2,2,3,3,4], the function should return the new lengthk = 9, andnumsThe first nine elements are0, 0, 1, 1, 2, 2, 3, 3, 4。

Key points:

• Ordered array:The input array is sorted, and using this feature to optimize the algorithm.
• Keep it up to twice:Each element is allowed to appear at most twice.
• Modify in place + O(1):The choice of algorithms is limited, and an algorithm with constant spatial complexity must be used.

V. Analysis and code implementation

5.1. Problem analysis

The problem can be broken down into the following sub-problems:

• Identify duplicates:How to effectively identify recurring elements? Since the array is ordered, the same adjacent elements are repeated.
• count:How to record the number of occurrences of each element? A variable is needed to track the number of occurrences of the current element.
• Modified in place:How to move elements that need to be retained to the front of the array without using extra space? Using the double pointer method is key.
• Update length:How to calculate and return the modified array length? The final position of the slow pointer + 1 is the new length.

Algorithm ideas:Based on the dual pointer method, combined with counters to solve this problem.

• Slow pointer (i）：Point to where the next element to be retained should be placed.
• Fast pointer (j）：Used to traverse the array and check whether the element should be preserved.
• counter(count）：Records the number of consecutive occurrences of the current element.

5.2. Algorithm implementation

Algorithm steps:

1. initialization:

   • i = 0(Slow pointer)
   • j = 0(Fast pointer)
   • count = 1(The initial count is 1, becausenums[0]Appear at least once)

2. Iterate over the array:

   • LoopjFrom 1 to - 1。
   • Situation 1:nums[j] == nums[j-1](Encounter with the same element)
     • count++(Increase the counter).
     • ifcount <= 2：Indicates that the current element is allowed to be retained.
       • Willnums[j]Copy tonums[i]Location (nums[i] = nums[j] )。
       • i++(Move slow pointer).
   • Situation 2:nums[j] != nums[j-1](Encounter different elements)
     • nums[i] = nums[j]
     • i++
     • count=1

3. Return result:After the cycle ends,iIt is the number of elements that should be retained in the array, so it returnsi。

Sample demonstration:Assumptionnums = [1,1,1,2,2,3]

Final result:nums = [1, 1, 2, 2, 3, ...],returni = 5

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = ();
        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;
    }
};

Complexity analysis:

• Time complexity:O(n), where n is the length of the array. It takes time to traverse the array.
• Space complexity:O(1), using additional space at constant level (i, j, count）。

5.3. Fast and Slow Pointer (recommended)

principle:

• slowThe initial value of the pointer is 2 because it means that the first two elements in the new array have been determined (i.e. the first two elements of the original array).
• fastThe pointer starts traversing the array from 2.
• ifnums[fast]andnums[slow - 2]Unequal, it meansnums[fast]can be added to a new array and assigned tonums[slow], and increment at the same timeslowPointer.
• ifnums[fast]andnums[slow - 2]Equal, it meansnums[fast]It is an extra repeating element, skip it directly.
• After the cycle ends,slowThe value of the pointer is the length of the new array.

Sample demonstration:Assumptionnums = [1,1,1,2,2,3]

Final result:nums = [1, 1, 2, 2, 3, ...],returnslow = 5

Code implementation:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = ();
        if (n <= 2) {
            return n; // Relative to less than or equal to two elements, return directly        }

        int slow = 2; // The slow pointer points to the next position to be placed, starting from the third position        int fast = 2; // Fast pointer is used to traverse arrays
        while (fast < n) {
            // If the current element is different from the first two elements of the slow pointer, it can be preserved            if (nums[fast] != nums[slow - 2]) {
                nums[slow] = nums[fast]; // Move the element pointed to by the fast pointer to the position of the slow pointer                slow++; // The slow pointer moves backward            }
            fast++; // The fast pointer always moves backward        }

        return slow; // The value of the slow pointer is the length of the new array    }
};

Complexity analysis:

• Time complexity:O(n), where n is the length of the array. You only need to iterate over the array once.
• Space complexity:O(1), using additional space at constant level (slow, fast）。

5.4. Inefficient code implementation

Idea: For repeating elements over 2 times, use a loop to move them to the end of the array using a loop.

The idea is correct, but there are some efficiency problems and potential mistakes. The core problem is that for each element that needs to be deleted, a loop move operation is performed, which will lead to excessive time complexity, especially when there are many repeating elements.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = ();
        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;
    }
};

6. Summary

The double pointer method is an effective way to solve such in-situ modification problems. By maintaining two pointers, one pointing to the position of the next unique element and the other for iterating through the array, we can efficiently delete duplicates and keep the relative order unchanged. Understanding the characteristics of sorting arrays is crucial to selecting the right algorithm.

The above is the detailed content of N methods for C++ to delete ordered array duplicates in place. For more information about C++ deleting ordered array duplicates, please pay attention to my other related articles!