“This is the first day of my participation in the First Challenge 2022. For details: First Challenge 2022.”
Hi, everybody. I’m handsome.
At the beginning of the array when I did not write actual combat, I thought array is so simple, what is good to write.
Until recently there are egg powder with me, I found myself xue Xue some floating.
Can write obviously a lot of!
This reminds me of the “curse of knowledge”, when one knows something and cannot imagine how it looks to the unknown.
I take it as a warning.
Because arrays are so common, I’m just going to pick a few types of problems, roughly the ones the reader is talking about.
You can add more when you think of something else.
Today’s solution to remove elements is a classic problem of fast and slow Pointers. Don’t say a word. Just turn it on.
LeetCode 27: Remove elements
The question
Given an array of nums and val, remove all values equal to val in place and return the new length of the array.
The sample
Input: nums = [0,1,2,2,3,0,4,2], val = 2
5, nums = [0,1,4,0,3]
Explanation: The function should return a new length of 5, and the first five elements in nums are 0, 1, 3, 0, 4. Notice that these five elements can be in any order. You don’t need to worry about the element after the new length in the array.
prompt
You must 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, easy topic.
This problem is equivalent to deleting an array element, since it involves deleting an array element, it is not taken for granted.
As I mentioned in the article “ACM Players take you to play with arrays” :
An array is a collection of data of the same data type stored in a contiguous segment of memory. Because of this “contiguous memory”, each element in the array is inserted or deleted while other elements are moved accordingly.
The data size of this problem array is small, up to 100, so it can be solved by brute force.
The brute force approach is the most mindless of all, a two-layer for loop. The first for loop iterates through the array starting at 0, and the second for loop maintains that the following elements move forward.
For example, the first layer for loop iterates to position 2 and finds nums[2] == val, then the second layer loop moves all elements at positions I +1 ~ n-1 forward one position.
Because it’s a double for loop, the time is O(n ^ 2).
Although also can AC, but obviously as the new era of three good men, this handsome egg in this aspect of the pursuit is not slow, but second man extreme, I want fast!
If I’m going to hurry, I’m going to have to do this.
Fast and slow Pointers, as the name suggests, use Pointers with different speeds (used on linked lists, arrays, sequences, etc.) to solve some problems.
The fast pointer fast refers to the element to be compared with val, and the slow pointer slow refers to the position to be assigned:
- Iterate over the number set.
- If the fast pointer points to the element nums[fast]! = val, nums[fast] is the element of the output array and is assigned to the position nums[slow]. Slow and fast move backwards by one bit at the same time.
- If nums[fast] == val, the current nums[fast] is the element to be deleted, and fast moves back one bit.
- Fast traverses the entire array, and the value of slow is the length of the remaining array.
The illustration
For example, nums = [0,1,2,2,3,0,4,2] and val = 2.
First initialize the fast and slow Pointers.
Initialize the pointer fast = slow = 0Copy the codeIterate through the array.
Step 1, fast = 0, slow = 0, nums[fast] = 0, not val.
At this point nums[slow] = nums[fast] (although they are already one), slow and fast move backwards one bit.
If the value of the fast pointer is not equal to the value of the element pointed to by val # fast, assign the value to the position pointed to by slow if nums[fast]! = val: nums[slow] = nums[fast] slow += 1 fast += 1Copy the codeStep 2, slow = 1, nums[fast] = 1, not val.
When nums[slow] = nums[fast], slow and fast move backwards one bit.
Step 3, fast = 2, slow = 2, nums[fast] = 2, equal to val.
At this point, fast moves back one bit and slow does not move.
If the fast pointer points to a value equal to val # move only the fast pointer, and do not assign fast += 1 to the slow pointerCopy the codeStep 4, slow = 2, nums[fast] is still 2, equal to val.
So again fast moves backwards, slow doesn’t move.
Step 5, slow = 2, nums[fast] = 3, not val.
When nums[slow] = nums[fast] = 3, slow and fast move backwards one bit.
Step 6, fast = 5, slow = 3, nums[fast] = 0, not equal to val.
When nums[slow] = nums[fast] = 0, slow and fast move backwards one bit.
Step 7, fast = 6, slow = 4, nums[fast] = 4, not equal to val.
When nums[slow] = nums[fast] = 4, slow and fast move backwards one bit.
Step 8, fast = 7, slow = 5, nums[fast] = 2, equal to val.
At this point, fast moves back one bit, slow does not change, and the array traversal ends.
As you can see, [0, slow) is the remaining output array, and slow is the length of the remaining array.
The solution of this problem uses a layer for loop, so the time complexity is O(n).
Two additional Pointers fast and slow are used, and 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: While fast < len(nums): If the value of the fast pointer is not equal to the value of the element pointed to by val # fast, assign the value to the position pointed to by slow if nums[fast]! = val: nums[slow] = nums[fast] slow += 1 #Copy the codeJava code implementation
Public int removeElement(int[] nums, int val) {class Solution {public int removeElement(int[] nums, int val) { int slow = 0; for (; fast < nums.length; fast++) { if (nums[fast] ! = val) { nums[slow] = nums[fast]; slow++; } } return slow; }}Copy the codeGraphic remove elements to this end hot, array combat first article, is not very feeling?
This is just an appetizer, and there’s more to come.
Please give me a thumbs up and make me feel better!
I’m Handsome. See you next time!