27. Remove the element

Given an array nums and a value val, you need to remove all elements equal to val in place, and return the new length of the removed array. Instead of using extra array space, you must modify the input array in place and do so using O(1) extra space. The order of the elements can be changed. You don’t have to worry about elements beyond the new length of the array.

The obvious solution is to use while + splice, but the splice operation is time-consuming, and each time you delete an element, you need to rearrange the elements in the array. Other operations that have the same side effects are unshift and shift. (You can see the V8 source code)

In comparison, pop and push are very fast operation methods. Here, double pointer + pop operation method can be adopted to further optimize the time complexity:

var removeElement = function(nums, val) {
  const max = nums.length
  let start = 0
  let end = max - 1
  while(start <= end) {
      if(nums[end] === val) {
          nums.pop()
          // The pop() method removes the last element from the array,
          // return the value of the element. This method changes the length of the array.
          end--
          continue
      }
      if(nums[start] === val){
          nums[start] = nums[end] // Assign the element with index end to start and delete end
          nums.pop()
          end--
          start++
          continue
      }
      start++
  }
  return nums.length
};
// Time complexity O (n)
// Space complexity O (1)
Copy the code

conclusion

The third day, the choice of force buckle 27, continue to learn the double pointer, refueling together wow ~

❤️ Thank you all

If you think this content is very helpful to you: like support, let more people can also see this content (collection does not like, is playing rogue – -) follow the public number to NPY front secret, we learn together progress. If you like it, you can also read other articles (thanks to friends for their encouragement and support 🌹🌹🌹)

Start the LeetCode tour

Double pointer to LeetCode