Leetcode Top100 Challenge, remove duplicates from an ordered array every day (17/100)

This is the 29th day of my participation in Gwen Challenge

Topic describes

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. Leetcode-cn.com/problems/re…

The sample1: Input: nums = [1.1.2] output:2, nums = [1.2The 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 sample2: Input: nums = [0.0.1.1.1.2.2.3.3.4] output:5, nums = [0.1.2.3.4The 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

The label

HashMap, double pointer

Analysis of the problem solving

1. HashMap

Let’s get right to it.

This problem is easy and difficult. There are many ways to do it. A hashMap, by definition, returns the length of the array to be reloaded, and the result of the nums to be reloaded. Create a map and traverse it in one go. The map saves the number that is not repeated, and then deletes it if it is in the map. But hashMap is not very efficient, so let's look at the code first.Copy the code

Go to ！！！！！

function removeDuplicates(nums: number[]) :number {
    const hashMap = new Map(a)let len = nums.length
    for(let i =0; i< len; i++) {
        if(hashMap.has(nums[i])) {
            nums.splice(i, 1)
            len = len -1 
            i = i - 1
        }
        else hashMap.set(nums[i], nums[i])
    }
    return nums.length
};
Copy the code

2. Double pointer

Let’s get right to it.

Fast and slow, old friend, two Pointers, slow to determine the non-repeating elements, fast to run, and basically that's it.Copy the code

Go to ！！！！！

function removeDuplicates(nums: number[]) :number {
    let  len = nums.length
    if(len === 0) return 0

    let fast = 1, slow = 1

    while(fast < len) {
        if(nums[fast] ! == nums[fast -1 ]) {
            nums[slow] = nums[fast]
            ++slow 
        }
        ++fast
    }
    return slow
};
Copy the code

The last

From today not pigeon, every day an algorithm problem and published articles, first want to solve the problem group for Top100, the seventeenth topic finished work!!