[algorithm - Primary - array] delete duplicate items in the sorting array (implemented in multilingual version)

🌶 Blog description and thanks

🎆🎆🎆 Part of the information involved in this article comes from the Internet, including my personal summary and views. The purpose of sharing is to build a community and consolidate myself.

💗💗💗 If there is infringement on the cited materials, please contact me to delete!

❤️ ‍ 🔥❤️ ‍ 🔥❤️ ‍ 🔥 Thanks for the universal network!

🥪🥪🥪 And industrious own，Personal blog，GitHub learning，GitHub

🍿🍿🍿 official account [Guizi Mo] , applet [Zi Mo said]

👍👍👍 If you feel helpful to you, you might as well give me some praise and encouragement. Remember to collect good articles! Pay attention to me and grow together!

💐💐💐 Luckily I'm here. Thank you for coming!

🍄 Algorithm description

Language is only a means to realize the algorithm, and the idea is the most important.

If there are multiple solutions, select only one language as the solution comparison.

If a single algorithm is used, it will be implemented in multiple languages to compare the characteristics of the language.

😎 Because many to many words, the length will be larger and affect the viewing experience!

🍖 subject

address

26. Delete duplicates in the ordered array

Give you an ordered array nums, please delete the repeated elements in place, make each element appear only once, and return the new length of the deleted array.

Title Description

Do not use additional array space. You must modify the input array in place and complete it with O(1) additional space.

explain

Why is the returned 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 the function is visible to the caller.

You can imagine the internal operation as follows:

// nums is passed by reference. That is, no copy of the arguments is made
int len = removeDuplicates(nums);

// Modifying the input array in the function is visible to the caller.
// According to the length returned by your function, it will print all elements within that length range in the array.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Example 1

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: the function should return a new length of 2 and the original array nums The first two elements of are modified to 1, 2 . There is no need to consider the elements in the array that exceed the new length.

Example 2

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: the function should return a new length of 5 and the original array nums The first five elements of are modified to 0, 1, 2, 3, 4 . There is no need to consider the elements in the array that exceed the new length.

Tips

0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums Sorted in ascending order

🥕 thinking

Violent thoughts

(note that it's a violent idea, not a violent solution!)

As a straight man, I just want to achieve.

Directly traverse to see if the title is determined to be orderly. If it is not equal to the previous one, directly get it to him and store it in a new array. After traversing the new array directly is the answer.

It seems to be very close! After all, it belongs to a simple topic.

However, we can't cross this barrier under the condition of O(1) additional space. In that case, you have to consider operating on the original array.

Operation on the original array, double pointers first!

Double pointer

thinking

The fast pointer is fast and the slow pointer is low.

If the array is ordered, the repeated elements must be adjacent. Operate in the same array, that is, move the non repeating elements to the left of the array, and finally take the value of the array on the left.

Algorithm flow

• Compare whether the elements at fast and low positions are equal.

  • Loop execution:

    • If equal, fast moves back 1 bit
    • If they are not equal, change the value of the previous bit of low to fast, move low by 1 bit and fast by 1 bit

  • End of cycle:

    • fast out of bounds
• At the end of the loop, the new array length low + 1 is returned

graphic

This will be the most soul moment. Algorithms without diagrams are hooligans! (hahaha, I will try my best to correct my previous rogue behavior, ha!)

In fact, drawing took me a lot of time, but I think it's not a loss. I remember it more deeply!

Let's have a GIF! (wrote a gadget to generate GIF from pictures in Python)

JavaScript

There's nothing particularly hard to say. The forced word is to take up the length calculation of nums to save costs.

code

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    // Judge boundary
    if (nums && nums.length < 0) {
        return 0
    }
    var low = 0, fast = 1, n = nums.length;
    while (fast < n) {
        if (nums[fast] !== nums[low]) {
          nums[low + 1] = nums[fast]
            low++  
        } 
        fast++
    }
    return low + 1
};

Java

code

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int fast = 1, low = 0, n = nums.length;
        while(fast < n) {
            if (nums[fast] != nums[low]){
                nums[low + 1] = nums[fast];
                low++;
            }
            fast++;
        }
        return low + 1;
    }
}

Python3

code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        fast = 1
        low = 0
        while fast < n:
            if nums[fast] != nums[low]:
                nums[low + 1] = nums[fast]
                low += 1
            fast += 1
        return low + 1

PHP

code

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function removeDuplicates(&$nums) {
        if ($nums == null || count($nums) < 0) {
            return 0;
        }
        $fast = 1;
        $low = 0;
        $n = count($nums);
        while ($fast < $n) {
            if ($nums[$fast] != $nums[$low]) {
                $nums[$low + 1] = $nums[$fast];
                $low++;
            }
            $fast++;
        }
        return $low + 1;
    }
}

Go

Note that the go language has no while

code

func removeDuplicates(nums []int) int {
    n := len(nums)
    if n < 1 {
        return 0
    }
    low := 0
    for fast := 1; fast < n; fast++ {
        if nums[fast] != nums[low] {
            nums[low + 1] = nums[fast]
            low++
        }
    }
    return low + 1
}

C++

code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n < 1) {
            return 0;
        }
        int fast = 1, low = 0;
        while (fast < n) {
            if (nums[fast] != nums[low]) {
                nums[low + 1] = nums[fast];
                low++;
            }
            fast++;
        }
        return low + 1;
    }
};

C

code

int removeDuplicates(int* nums, int numsSize){
    if(numsSize == 0) {
        return 0;
    }
    int fast = 1, low = 0;
    while (fast < numsSize) {
        if (nums[fast] != nums[low]) {
            nums[low + 1] = nums[fast];
            low++;
        }
        fast++;
    }
    return low + 1;
}

🥦 summary

Start with an array and think 🤔 Array proposes how to refine ideas, disassemble them step by step from simple to complex, and improve the data use skills of programming language.