Using fast and slow pointer method to solve the problem of array (C language)

Topic 1

Title source （ Power button ）： Remove elements

Title Description ：
Give you an array nums And a value val, You need In situ Remove all values equal to val The elements of , And return the new length of the array after removal .
Don't use extra array space , You have to use only O(1) Additional space and Modify the input array in place .
The order of elements can be changed . You don't need to think about the elements in the array that follow the new length .

Example ：
Input ：nums = [3,2,2,3], val = 3
Output ：2, nums = [2,2]

The problem is to remove the element with the specified value .

【 The basic idea 】
First the slow and fast All initialized to 0 .
（ fast Is the subscript used to indicate the position traversed currently ,slow Is the subscript used to indicate the position to be filled ）

When fast When an element to remove is encountered , Skip it （ take fast Move back one position ）.
When fast The encountered element is not to be removed , First the nums[fast] The value is assigned to nums[slow], let slow and fast Move all the way back .

Put the above into the following code .

int removeElement(int* nums, int numsSize, int val){
    
    int slow = 0, fast = 0;
    while(fast < numsSize)
    {
    
        if(nums[fast] != val)
            nums[slow++] = nums[fast++];
        else
            fast++;
    }

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

Topic two

Title source （ Power button ）： Remove duplicate items from an ordered array

Title Description ：
Here's an ordered array nums , Would you please In situ Delete duplicate elements , Make each element Only once , Returns the new length of the deleted array .
Don't use extra array space , You must be there. Modify the input array in place And using O(1) Complete with extra space .

Example ：
Input ：nums = [0,0,1,1,1,2,2,3,3,4]
Output ：5, nums = [0,1,2,3,4]

This problem is to delete the repeated elements , Make different elements appear only once .

【 The basic idea 】
First the slow and fast They are initialized to 0 and 1 .

Through the analysis of , There are two situations ：
Situation 1 ： If fast The element pointing to the position follows slow The elements pointing to the position are different , First, let slow Move back one position , And then nums[fast] The value is assigned to nums[slow], Finally let fast Move back one position .
Situation two ： If fast The element pointing to the position follows slow The elements pointing to the position are equal , Description there are duplicates , Just put the fast Move back one position , Repeat this step until case one .

（ fast Is the subscript used to indicate the position traversed currently ,slow Is the subscript used to indicate the position to be filled ）

The above two cases are sorted into the following codes .

int removeDuplicates(int* nums, int numsSize){
    
    if(numsSize == 0) // If the array  nums  The length of is  0, That is, the array does not contain any elements , return  0.
        return 0;

    int slow = 0, fast = 1;
    while(fast < numsSize)
    {
    
        if(nums[fast] != nums[slow])
        {
    
            ++slow;
            nums[slow] = nums[fast];
        }

        ++fast;
    }

    return slow + 1;   // The new length of the last array is  slow + 1
}

This ensures that
The subscript range is [0, slow] The array elements of are all processed non duplicates ,
The subscript range is [slow + 1, fast - 1] The array elements of are duplicates of the previous array elements .

More articles
The wonderful use of XOR （C Language ）
Add large numbers （C Language ）
Merge two ordered arrays （C Language ）
Zero after factorial （C Language ）
Adjust the array order so that the odd Numbers precede the even Numbers （C Language ）