How to solve the problem of removing elements in leetcode
This article is about how to solve the problem of removing elements in leetcode. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.
Topic link
Https://leetcode-cn.com/problems/remove-element/
Topic description
Given an array nums and a value val, you need to remove all elements whose values are equal to val in place and return the new length of the removed array.
Do not use extra array space, you must modify the input array in place and do it using O (1) extra space.
The order of elements can be changed. You don't need to consider the elements in the array that exceed the new length.
Example 1:
Given nums = [3pm 2pm 2pm 3], val = 3
The function should return a new length of 2, and the first two elements in nums are both 2.
You don't need to consider the elements in the array that exceed the new length.
Example 2:
Given nums = [0meme1jin2], val = 2], val = 2
The function should return the new length 5, and the first five elements in nums are 0, 1, 3, 0, 4.
Note that these five elements can be in any order.
You don't need to consider the elements in the array that exceed the new length. The first way of thinking of the solution to the problem
Tags: copy overlay
The main idea is to traverse the array nums, fetching the number variable num each time, and setting a subscript ans at the same time
If the number does not match the value to be removed during traversal, copy and overwrite nums [ans] = num,ans increment 1
If the same time, skip the number without copy overwriting, and finally ans is the new array length
This idea is more suitable to use when there are more elements removed. In the most extreme case, all elements need to be removed and can be traversed.
Time complexity: O (n), space complexity: O (1)
The first code
Java version
Class Solution {
Public int removeElement (int [] nums, int val) {
Int ans = 0
For (int num: nums) {
If (num! = val) {
Nums [ans] = num
Ans++
}
}
Return ans
}
}
JavaScript version
/ * *
* @ param {number []} nums
* @ param {number} val
* @ return {number}
, /
Var removeElement = function (nums, val) {
Let ans = 0
For (const num of nums) {
If (num! = val) {
Nums [ans] = num
Ans++
}
}
Return ans
}
The second way of thinking
Tags: swap removal
The main idea is to traverse the array nums, the traversal pointer is I, and the total length is ans
If the number is not the same as the value to be removed during traversal, I will increase by 1 and continue the next traversal.
If the same time, swap nums [I] with nums [ans-1], that is, the current number is swapped with the last number in the array, and one element is missing after the exchange, so ans minus 1.
This idea is more suitable to use when fewer elements are removed. In the most extreme case, no elements need to be removed. Just go through it and finish it.
Time complexity: O (n), space complexity: O (1)
The second code
Java version
Class Solution {
Public int removeElement (int [] nums, int val) {
Int ans = nums.length
For (int I = 0; I
< ans;) { if (nums[i] == val) { nums[i] = nums[ans - 1]; ans--; } else { i++; } } return ans; } } JavaScript版本 /** * @param {number[]} nums * @param {number} val * @return {number} */ var removeElement = function(nums, val) { let ans = nums.length; for (let i = 0; i < ans;) { if (nums[i] == val) { nums[i] = nums[ans - 1]; ans--; } else { i++; } } return ans; }; 画解
Thank you for reading! This is the end of this article on "how to solve the problem of removing elements in leetcode". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it for more people to see!
