Removes duplicates from an array

Given a sorted array, you need to remove duplicate elements in place so that each element appears only once, returning the new length of the removed array.

Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.

Example 1:

Given the array nums = [1,1,2], the function should return a new length of 2, and the first two elements of the original array nums are changed to 1,2. You don't need to worry about the element after the new length in the array.Copy the code

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4], the function should return a new length of 5, and the first five elements of the original nums array are modified to 0,1, 2,3, 4. You don't need to worry about the element after the new length in the array.Copy the code

Description:

Why is the return value an integer, but the output answer is an array?

Note that the input array is passed by ** “reference” **, which means that modifying the input array within the function is visible to the caller.

You can imagine the internal operation as follows:

// Nums is passed by reference. That is, it does not make any copies of the arguments int len = removeDuplicates(nums); // Modifying the input array in a function is visible to the caller. // Depending on the length returned by your function, it prints out all elements in the array within that length.for (int i = 0; i < len; i++) {
    print(nums[i]);
}
Copy the code

Train of thought

The key point

  1. Sorting data
  2. Do not use extra array space
  3. Delete duplicate elements in place

To solve the problem

  • Define nums[0] as a parity bit int cur = nums[0], and loop through the array from index 1

  • Compares the checksum bit cur in turn with the value of each index position in the array

The first time you compare two values equal, you don’t change them

A second comparison of NUMS [2]! = cur

Replace the element position with nums[2] and declare an int curIndex = 1; Nums [2] is assigned to the value of nums[curIndex].

The red dotted box in the figure above is already non-repeating data

Move index and curIndex back one bit at a time, and then loop, where the cur bit becomes 2

Third cycle comparison

The flag bit cur is equal to nums[3], indicating that it is a repeated element. The element in NUMs [3] has already appeared in the red dotted box

Move index back one bit, curIndex stays the same, the contents of the red dotted box remain the same, and the cur identifier bit remains the same

Fourth cycle comparison

At this point, the flag bit is not equal to nums[4], and as in step 2, the element at nums[curIndex] and cur needs to be replaced

Move index and curIndex back one bit at a time

The fifth cycle comparison

The flag bit cur is equal to nums[5], indicating that it is a repeated element. The element in NUMs [5] has already appeared in the red dotted box

Move index back one bit, curIndex stays the same, the contents of the red dotted box remain the same, and the cur identifier bit remains the same

The sixth cycle comparison

Not equal. Replace the element at curIndex

And move back curIndex = curIndex + 1

The last position at curIndex is the solution to the problem

code

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        
        int cur = nums[0];
        int index = 1;
        
        for (int i = 1; i < nums.length ; i ++) {
            if(cur != nums[i]){
                nums[index ++] = nums[i];
                cur = nums[i];
            }
        }
        returnindex; }}Copy the code