Title link: leetcode-cn.com/problems/re…

Methods a

Their thinking

  • The main idea is to traverse a set of numbersnums, the array element extracted each time isnum, set the initial subscript toans.
  • In traversal, ifnumIf the value is different from the value to be removed, copy overwrite the valuenums[ans] = num.ansSince the increased 1.
  • If they are the same, the number is skipped and not overwrittenansIs the new array length.
  • This idea works for a large number of elements that need to be removed. In the most extreme case, all elements need to be removed, and the end of the loop is complete.

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

Complexity analysis:

  • Time complexity:
  • Space complexity:

Method 2

Their thinking

Now consider the case where the array contains very few elements to delete. For example,.. The previous algorithm made unnecessary copies of the first four elements. Here’s another example.. There seems no need toThe elements are moved one step to the left because the order in which the elements are mentioned in the problem description can be changed.

Therefore, we can solve this problem by saying that when we encounter nums[I] = val, we can swap the current element with the last one and release the last one. This actually reduces the size of the array by 1.

Note that the last element swapped may be the value you want to remove. But don’t worry, we’ll still check this element in the next iteration.

code

/** * @param {number[]} nums * @param {number} val * @return {number} */
var removeElement = function(nums, val) {
    let ans = nums.length;
    for (i = 0; i < ans;) {
        if (nums[i] == val) {
            nums[i] = nums[ans - 1];
            ans--;
        } else {
            i++
        }
    }
    return ans;
};
Copy the code

Complexity analysis:

  • Time complexity:
  • Space complexity:

More questions please pay attention to: github.com/leviding/le…

Pay attention to the public number “technology chatter” plus algorithm group, every day an algorithm, fun algorithm is very easy! :

  • LeetCode algorithm problem solving
  • JavaScript getting started to advanced
  • Front-end projects go from zero to one
  • Front end learning method route sharing
  • …