26. Remove duplicates from sorted array

Topic:

Given a sorted array, you need to remove duplicate elements in place so that each element appears only once, returning the new length of the removed array. Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space. Example:

The sample1Given array nums = [1.1.2], the function should return the new length2, and the first two elements of the original array NUMs are modified to1.2. You don't need to worry about the element after the new length in the array.The sample2Given nums = [0.0.1.1.1.2.2.3.3.4], the function should return the new length5, and the first five elements of the original array NUMs are changed to0.1.2.3.4. You don't need to worry about the element after the new length in the array.Copy the code

Their thinking

Extract important nouns from the topic, sort the array, delete in place, return the length, and do not use extra array space. In other words, we need to:

  1. Sort: Array ordered.
  2. De-weight: De-weight the ordered array, just need to determine whether the number before and after the same.
  3. Delete in place: You must operate on the original array.
  4. Return length: Returns the length instead of the deduplicated array.

code

Brute force method

/** * @param {number[]} nums * @param {number} target * @return {number[]} */
 var removeDuplicates = function(nums) {
  for(var i = 0; i < nums.length; i++){if(nums[i+1] != 'undefined' && nums[i+1] === nums[i]){   // Check whether it is equal before and after
          let index = nums.indexOf(nums[i]);
          nums.splice(index,1);  // delete in place
          i = i- 1; }}return nums.length;  // Returns the length
};
Copy the code

Brute force cracking is to grab those keywords and implement them one by one. However, we can see that in the for loop we need to use indexOf for lookups, and then splice for splits, both of which have O(n) levels at the bottom. So can we do something simpler? At this point, we need to review the topic to see if we missed any other key information. We saw several times in the example that you don’t need to worry about the elements in the array beyond the new length, just make sure that the first n elements of the original array can be de-weighted. What does that mean? Before we removed the duplicate element in place, we had to find the element through indexOf and then delete it at its location. Now we can just find the non-repeating elements in the array and move those non-repeating elements to the front of the array, and we don’t care if the following elements are duplicated.

var removeDuplicates = function(nums) {
  var len = 0;
  for(var i = 0; i < nums.length; i++){if(nums[i+1] != 'undefined' && nums[i+1] !== nums[i]){
         nums[len] = nums[i]; 
         len+=1; }}return len;
};
Copy the code

All we need to do is define a pointer to the current position of the non-repeating element in the array. If we find the non-repeating element, we assign it to the next position.

This article is formatted using MDNICE