Removes duplicates from an ordered array

Give you an ordered array nums, ask you to delete the repeated elements in place, so that each element appears only once, return the deleted array after the new length. Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.

 

• 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 in a function is visible to the caller. You can imagine the internal operation as follows:

  Nums are passed “by reference”. That is, do not make any copies of the arguments

    int len = removeDuplicates(nums);
  Copy the code

  Modifying the input array in a function is visible to the caller. Depending on the length returned by your function, it will print out all elements in the array within that length range.

    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }
  Copy the code

 

• Example 1:

  Input: nums = [1,1,2] Output: 2, nums = [1,2] Explanation: The function should return a new length of 2, and the first two elements of the original array nums are changed to 1,2. You don't need to worry about the element after the new length in the array.Copy the code

• Example 2:

  Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2, 2,3,4] Explanation: The function should return a new length of 5, and the first five elements of the original array NUMs are modified to 0,1,2,3,4. You don't need to worry about the element after the new length in the array.Copy the code

My way of thinking about solving this problem

Delete duplicates from an array. Delete duplicates from an array.

Compare the first item with the second, remove the second item from the array if they are the same, compare the first item with the third, and so on. From here, I find that this is similar to the idea of “simple sorting”, and write a concrete framework based on this:

for(var i = 0; i<nums.length; i++) { for(var j = i+1; j<nums.length; j++) { } }Copy the code

To delete unwanted elements, use splice() :

    if(nums[i] === nums[j])
    {
    nums.splice(j,1);
    }
    
Copy the code

Here’s the key:

When we delete an element, the length of the array is -1, but the value of j does not change, so there will be omissions in judging whether the array is the same or not. For example, the length of the array is 6, the value of I is 2, and the value of j is 3. Assume that nums[2] = nums[3], then nums[3] needs to be deleted. After deletion, the length of array becomes 5, but the length of j does not change. A NUMS [3] is omitted from the comparison. So you have to subtract j by 1 after you delete the element.

• The code looks like this (this method is a bit cumbersome)

  /** * @param {number[]} nums * @return {number} */ var removeDuplicates = function(nums) { for(var i = 0; i<nums.length; i++) { var a = nums.length; console.log(nums.length); for(var j = i+1; j<a; J++) / / the nums. Change length {the if (nums = = = [I] nums [j]) {nums. Splice (j, 1); j-- } } } return nums.length; };Copy the code

Other solutions I saw in Leetcode:

The first:

function removeDuplicates(nums){ if(nums==null || nums.length == 1){ return nums.length; } var i = 0,j =1; while(j<nums.length){ if(nums[i]==nums[j]){ j++; }else{ i++; nums[i]=nums[j]; // override j++ directly; } } return i+1; }Copy the code

The second:

function removeDuplicates(nums){ if(nums.length < 2){ return nums.length; } var i = 0; for(var j = 1; j<nums.length; j++){ if(nums[j] ! = nums [I]) nums [+ + I] = nums directly covered} [j] / / return + + I; }Copy the code

Here are two ways to solve the problem:

Nums [0] is first used as a comparison object to compare the following items. If not, nums[j] is directly assigned to nums[1], and then the untraversed numbers are compared with nums[1], and so on. Finally, since the maximum index of the array is 1 less than the array length, we return +1;

• Conclusion:

The whole idea is similar to the following two ways, which is to iterate through a set of numbers to get different values.

The difference is that I did a lot of useless work with the “simple sort” algorithm, and I used split() to delete the same parts of the array, which then changed the length of the original array. Therefore, it is necessary to consider the effect of the array length shortening after deletion, and the following two methods use direct overwrite. The array length does not change.

Small white one, still ask everybody big guy a lot of advice