• Personal blog: Javaniuniu.com/
  • Difficulty:simple
  • The problem involves the algorithm:
  • Ideas:Double pointer method
  • Similar questions:

The title26. Remove duplicates from sorted array

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)O(1)O(1) extra space.

Example 1:

Given the array nums = [1,1,2], 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:

Given nums = [0,0,1,1,1,2,2,3,3,4], the function should return a new length of 5, and the first five elements of the original nums array 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

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 is passed by reference. That is, it does not make any copies of the arguments int len = removeDuplicates(nums); // Modifying the input array in a function is visible to the caller. // Depending on the length returned by your function, it prints out all elements in the array within that length. for (int i = 0; i < len; i++) { print(nums[i]); }Copy the code

Method one is double pointer method

  • How to solve the problem:

    • After sorting the array, we can place two Pointers iii and JJJ, where III is the slow pointer and JJJ is the fast pointer. As long as nums[I]=nums[j]nums[I]=nums[j]nums[I]=nums[j], we add JJJ to skip duplicates.

    • If nums[j]≠nums[I]nums[j] \neq nums[I]nums[j]=nums[I] So we must copy the value of (nums[j]) (nums[j]) (nums[j]) to nums[I +1]nums[I +1]. Then increment III, and we repeat the same process again until JJJ reaches the end of the array.

  • Complexity analysis:

    • Time complexity: O(n)O(n)O(n), assuming that the length of the array is NNN, then III and JJJ traverse at most NNN steps, respectively.
    • Space complexity: O(1)O(1)O(1).

python

class Solution:
    def removeDuplicates(self, nums: List[int]) - >int:
        j = 0
        for i in range(1.len(nums)):
            ifnums[i] ! = nums[j]: j +=1
                nums[j] = nums[i]
        return j+1

Copy the code

java

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for(int j = 1; j<nums.length; j++) {if(nums[j] != nums[i]) {
                i ++ ;
                nums[i] = nums[j];
            }
        }
        return i + 1; }}Copy the code