[leetcode] 26. Delete duplicates in the ordered array

26、 Remove duplicate items from an ordered array

subject ：

To give you one Ascending order Array of nums , Would you please In situ Delete duplicate elements , Make each element Only once , Returns the new length of the deleted array . Elemental Relative order It should be maintained Agreement .

Because the length of an array cannot be changed in some languages , So you have to put the result in an array nums The first part of . More formally , If there is... After deleting duplicates k Elements , that nums Of front k individual Element should save the final result .

Insert the final result into nums Of front k Return to... After a position k .

Don't use extra space , You must be there. In situ Modify input array And using O(1) Complete with extra space .

Criteria for judging questions :

The system will use the following code to test your solution :

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

int k = removeDuplicates(nums); //  call 

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

Example 1：

 Input ：nums = [1,1,2]
 Output ：2, nums = [1,2,_]
 explain ： Function should return the new length  2 , And the original array  nums  The first two elements of are modified to  1, 2 .
 You don't need to think about the elements in the array that follow the new length .

Example 2：

 Input ：nums = [0,0,1,1,1,2,2,3,3,4]
 Output ：5, nums = [0,1,2,3,4]
 explain ： Function should return the new length  5 ,  And the original array  nums  The first five elements of are modified to  0, 1, 2, 3, 4 .
 You don't need to think about the elements in the array that follow the new length .

Tips ：

1 <= nums.length <= 3 * 10 ^4
-10 ^4 <= nums[i] <= 10 ^4
nums Pressed Ascending array

Their thinking ：

1. Due to the given array nums Is ordered , So for any i<j, If nums[i]=nums[j], For any
   i≤k≤j, There must be nums[i]=nums[k]=nums[j], That is, the subscripts of equal elements in the array must be continuous . Using the characteristics of array order , Duplicate elements can be deleted by double pointer method .
2. If the array nums The length of is 0, Then the array does not contain any elements , Therefore return 0.
3. Array nums Is longer than 0 when , The array contains at least one element , At least one element remains after deleting the duplicate element , therefore nums[0] Just keep it as it is , From the subscript 1 Start removing duplicate elements .
4. Define two pointers fast and slow Respectively Fast pointer and slow pointer , The fast pointer indicates the subscript position reached by traversing the array , The slow pointer indicates the subscript position to be filled in by the next different element , Initially, both pointers point to the subscript 1.
5. Hypothetical array nums The length of is n. Fast pointer fast Go through from 1 To n−1 Each location of , For each location , If
   nums[fast] !=nums[fast−1], explain nums[fast] Different from the previous elements , So it will nums[fast] Copy the value of to nums[slow], And then slow The value of the add 1, That is to point to the next position .
   After the traversal , from nums[0] To nums[slow−1] Of Each element is different and contains each different element in the original array , So the new length is slow, return slow that will do .

Reference code ：

class Solution {
    
    public int removeDuplicates(int[] nums) {
    
        int n = nums.length;
        if (n == 0) {
    
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
    
            if (nums[fast] != nums[fast - 1]) {
    
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}