The title

Removes duplicates from an ordered array

Leetcode-cn.com/problems/re…

The public account “Java Programming Notes” record Java learning daily, share learning road dribs and drabs, from entry to give up, welcome to pay attention to

describe

Difficulty: Easy

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 is passed by reference. That is, do 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

Example 1:

Enter: 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.Copy the code

Example 2:

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

Tip:

0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104Nums are sorted in ascending orderCopy the code

Solution

Double pointer solution

Their thinking

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.

  • Because it’s an ordered array, you don’t have to worry about the same values being separated, for example212In this case, if they are not ordered, they can be sorted
  • We’re going to modify the array in place, so we’re going to set up two concepts
    • New array, deleted array
    • Old array, old array passed in
  • Essentially, the old array and the new array are the same array, except that the Pointers are traversed to different places in the array
    • A pointer toThe new arrayThe latest location of the composition
    • A pointer toThe old arrayThe latest position traversed
  • Iterate over the old array, comparing each element with the new one
    • whennums[i] == nums[a], the elements are equal,aThe pointer does not move, and the I pointer continues to traverse
    • whennums[i] ! = nums[a], elements are not equal,aPointer moves back, assigns new after moving backnums[a], the pointer continues to traverse
    • Traverse the end
  • Returns the resulta+1Because theafrom0So you start to calculate, and you end up calculating the length+ 1

Initialization, a= 0, nums[a] = 1, traverses the old array, and the I pointer moves back with each comparison until the end

Nums [a] compares nums[I] with nums[I]

Nums [a] and nums[I] are compared, and the same elements are skipped

If not repeated, a++ is continued and nums[a] is assigned until the end

CODE

class Solution {
    public int removeDuplicates(int[] nums) {
      	// New array pointer a, starting at subscript 0 by default
        int a = 0;
        int len = nums.length;
      	// The old array pointer I starts at 1 by default
        for(int i=1; i<len; i++){// If the old pointer points to the same value as the new pointer, the new pointer does not move
            if(nums[i]==nums[a]){
              	/ / to skip
                continue;
            }else{
              	// The old and new Pointers point to different values. We need to move the new array pointer back and set the new value
              	/ / move backward
                a=a+1;
              	// Set the new valuenums[a] = nums[i]; }}// Since a starts at 0, we need +1 to compute the length
        return a+1; }}Copy the code

The complexity of the

  • Time complexity:O(N), N is the array length, traversing the array length once
  • Space complexity:O(1), in the array itself, no other memory space overhead

The results of

  • Execution time:1Ms, at allJavaDefeated in submission81.15% of the user
  • Memory consumption:39.6MB at allJavaDefeated in submission99.57% of the user

LeetCode:

A fierce operation such as tiger, a look to beat five percent