Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The question to describe

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.

Example 1:

Input: nums = [1,2] output: 2, nums = [1,2]

Explanation: The function should return a new length of 2, and the first two elements of the original nums array should be changed to 1, 2. You don’t need to worry about the element after the new length in the array.

Example 2:

Input: nums =,0,1,1,1,2,2,3,3,4 [0] output: 5, nums =,1,2,3,4 [0]

Explanation: The function should return a new length of 5, and the first five elements of the original nums array are changed to 0, 1, 2, 3, 4. You don’t need to worry about the element after the new length in the array.

Idea 1: Dual Pointers

Analysis:

  • The array is ordered, there is no case [0, 1, 1, 2, 3, 1, 1]
  • Operates on the array nums to be processed, moves the non-repeating elements to the left, and finally obtains the total number of non-repeating array newLength from nums[0] to nums[newLength-1].
class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int i = 0, j = 1;
        while(j<=nums.length-1) {
            if(nums[i] ! = nums[j]) {if(i + 1 < j) {
                    nums[i+1] = nums[j]; 
               }
               i = i+1;
            }
            j = j+1;
        } 
        return i+1; }}Copy the code

Idea 2: Recursion

public static int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int j = 0;
    int i = 0;
    int next = nextDiff(nums, nums[i], i);
    while (next > 0) {
        j++;
        nums[j] = nums[next];
        next = nextDiff(nums, nums[next], next);
    }
    return j+1;
}

private static int nextDiff(int[] newArray, int val, int start) {
    if (start == newArray.length - 1) {
        return 0;
    }
    start++;
    if (newArray[start] == val) {
        return nextDiff(newArray, val, start);
    } else {
        returnstart; }}Copy the code