1. Topic description

Title address

Title description:

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:

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
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

2

Method: double pointer

Train of thought

  • Purpose:The idea is simple, just define this as aA non-repetitive sorted array“, and then iterate over the array, maintaining the definition over and over again. Similar topics can refer to the following topics, using almost exactly the same idea.
    • 283. Move zero
    • 【No.2】【LeetCode series 】【 array 】
  • Define a pair of Pointers P1 and P2. The initial states p1 and P2 point to the top of the array, and p2 starts moving backwards. At this point, compare the elements p1 and p2 point to. If the element P2 points to is not equal to the element P1 points to, assign the value of p2 to P1, and both p1 and P2 point to the next element. If p2 points to an element equal to p1, then P1 does not move, and P2 continues to move.

Code implementation

public int removeDuplicates(int[] nums) { if (nums.length <= 1) { return nums.length; } int p1 = 0; int p2 = p1 + 1; while (p2 < nums.length) { if (nums[p2] ! = nums[p1]) { nums[p1 + 1] = nums[p2]; p1++; } p2++; } return p1 + 1; }Copy the code

Complexity analysis

  • Time complexity: O(n). There are n elements, and p1 and P2 take at most 2n steps.
  • Space complexity: O(1). You just need constant space for a few variables.

The execution result This article is participating in the “Nuggets 2021 Spring recruiting campaign”, click to seeEvent details