27. Remove elements

This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

The title

Leetcode-cn.com/problems/re…

Given an array of nums and a value of val, you remove all elements equal to val in place and return the new length of the array.

Instead of using extra array space, you must only use O(1) extra space and modify the input array in place.

The order of elements can be changed. You don’t need to worry about the element after the new length in the array.

Description:

Why is the return value an integer, but the output answer is an array?

Note that the input array is passed by ** “reference” **, which means that modifying the input array within the function is visible to the caller.

You can imagine the internal operation as follows:

// Nums is passed by reference. That is, no copies of the arguments are made

int len = removeElement(nums, val);

// Modifying the input array in a function is visible to the caller.

// Depending on the length returned by your function, it prints out all elements in the array within that length.

for (int i = 0; i < len; i++) {

print(nums[i]);

}

Example 1:

Enter nums = [3,2,2,3], val = 3

Output: 2, nums = [2,2]

Explanation: The function should return a new length of 2, and the first two elements in nums are both 2. You don’t need to worry about the element after the new length in the array. For example, the function returns a new length of 2, and nums = [2,2,3,3] or nums = [2,2,0,0] will also be considered the correct answer.

Example 2:

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.

Tip:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

Their thinking

Idea 1

Label: Copy overwrite
The main idea is to iterate over nums, each time the number variable is num, and set a subscript ANS
In the traversal process, if the number is different from the value to be removed, copy and overwrite the numbernums[ans] = num, ans increases by 1
If the values are the same, the number is skipped, and ans is the new array length
This approach works best when a large number of elements need to be removed, and the most extreme case is when all elements need to be removed
Time complexity: O(n)O(n)O(n), space complexity: O(1)O(1)O(1)

code

/ * * *@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;
};
Copy the code

Idea 2

Tags: Swap removed
The main idea is to iterate over nums, traversal pointer is I, total length is ANS
If there is a difference between the number and the value to be removed during the traversal, I increases by 1 to continue the next traversal
If the time is the same, thenNums [I] and nums [ans - 1)Swap, that is, the current number is swapped with the last number in the array, and one element is lost, so ans is reduced by one
This approach is best used when there are few elements to remove, and the most extreme case is when there are no elements to remove and you just iterate
Time complexity: O(n)O(n)O(n), space complexity: O(1)O(1)O(1)

code

/ * * *@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;
};
Copy the code