ACM Player Illustration leetcode remove element

Hello, everyone , I'm handsome .

At first, when talking about arrays, I didn't write practical problems , At that time, I thought that arrays were so simple , What's there to write about .

Until recently, some egg powder told me , I found out that it was myself xue xue Some of them are gone .

I can write a lot ！

It reminds me “ The curse of knowledge ”, When a person knows something , I can't imagine what it looks like in the eyes of the unknown .

I take it as a warning .

---

Because arrays are so commonly used , I'll pick out several types of questions , It's about the readers in the picture .

Think of something else later and continue to add .

Today's solution Remove elements , yes Classic topic of fast and slow pointer . Don't talk much , Direct alignment .

LeetCode 27： Remove elements

The question

Give you an array nums And a val, Remove all values in place equal to val Value , And return the new length of the array after removal .

Example

Input ：nums = [0,1,2,2,3,0,4,2], val = 2

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

explain ： Function should return the new length 5, also nums The first five elements in are 0, 1, 3, 0, 4. Note that these five elements can be in any order . You don't need to think about the elements in the array that follow the new length .

Tips

You have to use O(1) Space complexity and modify the input array in place .

• 0 <= len(nums) <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

title

Water problem , The title is simple. .

This problem is equivalent to the deletion of array elements , Since it involves the deletion of arrays , It's not like deleting it for granted .

I'm in the article 【ACM Players take you around the array 】 In the said ：

The array is made with A contiguous segment of memory space , To store the same data type A collection of data . Because of this “ Continuous memory storage ”, Make the array insert or delete elements , Other elements have to move accordingly .

The amount of data in this problem array is very small , Only... At most 100 individual , So you can use violence to crack .

The so-called violence is the most mindless way , Two layers of for loop , first floor for Cycle from 0 Start traversing array , The second floor for The element after the loop maintenance moves forward .

Like the first floor for Loop through to the subscript 2 Location found nums[2] == val, Then the second cycle will i+1 ~ n -1 All elements in position move forward one position .

Because it's double for loop , The time complexity is O(n²).

Although it can AC, But obviously, as the three good men of the new era , Ben Shuai egg's pursuit in this respect is certainly not slow , But the acme of second man , I want to hurry ！

If you want me to hurry up , I have to mention Speed pointer 了 .

Speed pointer , seeing the name of a thing one thinks of its function , Is to use pointers with different speeds （ Can be used in linked lists 、 Array 、 Sequence, etc ）, To solve some problems .

The speed pointer uses fast and slow Two pointers control , Quick pointer fast Point to the current and val Elements of contrast , Slow pointer slow Point to the position to be assigned ：

• Traversal array .
• If fast The element that the pointer points to nums[fast] != val, be nums[fast] Is the element of the output array , Assign it to nums[slow] The location of ,slow and fast Move back one bit at the same time .
• If nums[fast] == val, Prove the present nums[fast] Is the element to be deleted ,fast Move back a bit .
• fast Traverse the entire array , end ,slow The value of is the length of the remaining array .

The illustration

With nums = [0,1,2,2,3,0,4,2], val = 2 For example .

Initialize first fast and slow The pointer .

#  Initialize speed pointer 
fast = slow = 0

Traverse the entire array .

The first 1 Step ,fast = 0,slow = 0, here nums[fast] = 0, It's not equal to val.

here nums[slow] = nums[fast]（ Although they are one now ）,slow and fast Move back a bit .

#  If the value pointed to by the fast pointer is not equal to  val
# fast  The element pointing to the position points to  slow  Assign a value to the position pointed to 
if nums[fast] != val:
    nums[slow] = nums[fast]
    slow += 1
    fast += 1

The first 2 Step ,fast = 1,slow = 1, here nums[fast] = 1, It's not equal to val.

here nums[slow] = nums[fast],slow and fast Move back a bit .

The first 3 Step ,fast = 2,slow = 2, here nums[fast] = 2, be equal to val.

here fast Move back a bit ,slow Immobility .

#  If the fast pointer points to a value equal to  val
#  only  fast  The pointer moves , No direction  slow  The position pointed to by the pointer is assigned 
fast += 1

The first 4 Step ,fast = 3,slow = 2, here nums[fast] Is still 2, be equal to val.

So still fast Move back a bit ,slow Immobility .

The first 5 Step ,fast = 4,slow = 2, here nums[fast] = 3, It's not equal to val.

here nums[slow] = nums[fast] = 3,slow and fast Move back a bit .

The first 6 Step ,fast = 5,slow = 3,nums[fast] = 0, It's not equal to val.

here nums[slow] = nums[fast] = 0,slow and fast Move back a bit .

The first 7 Step ,fast = 6,slow = 4,nums[fast] = 4, It's not equal to val.

here nums[slow] = nums[fast] = 4,slow and fast Move back a bit .

The first 8 Step ,fast = 7,slow = 5,nums[fast] = 2, and val equal .

here fast Move back a bit ,slow unchanged , End of array traversal .

It can be seen that , here from [0, slow) For the rest of the output array ,slow The value of is the length of the remaining array .

The solution to this problem , Used a layer for loop , therefore The time complexity is O(n).

Two extra pointers are used fast and slow, The space complexity is O(1).

Code implementation

Python Code implementation

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
​
        if len(nums) == 0:
            return 0
        #  Initialize speed pointer 
        fast = slow = 0
​
        while fast < len(nums):
            #  If the value pointed to by the fast pointer is not equal to  val
            # fast  The element pointing to the position points to  slow  Assign a value to the position pointed to 
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            
            #  If the fast pointer points to a value equal to  val
            #  only  fast  The pointer moves , No direction  slow  The position pointed to by the pointer is assigned 
            fast += 1
​
        return slow

Java Code implementation

class Solution {
    public int removeElement(int[] nums, int val) {
        //  Initialize speed pointer 
        int fast = 0;
        int slow = 0;
        for (; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
​
    }
}

---

The diagram removes elements That's the end , Array combat first article , Do you feel it ？

It's just an appetizer , The wonderful topic is still behind .

Remember to help me give the thumbs-up ah , Let me feel numb ！

I'm handsome , I'll see you next time ！