Leetcode and Lintcode

Remove Duplicates from Sorted Array

Problem:

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

Example
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Tags Expand

Related Problems Expand

Leetcode link
lintcode link

My Solution:

In this question, a variable named ‘last’ is used to record the index of last element in the result array.
Go through the array, if the current element nums[i] is not equal to the last element of result array ‘nums[last]’,
add the current element to end of result array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*************************************************************************
    > File Name: RemoveDuplicate2.java
    > Author: Yao Zhang                                                                                                                                                              
    > Mail: psyyz10@163.com
    > Created Time: Thu 29 Oct 15:26:17 2015
 ************************************************************************/

public class RemoveDuplicate {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
 
        int last = 0;
 
        for (int i = 1; i < nums.length; i++){
            if (nums[last] != nums[i]){
                nums[++last] = nums[i];
            }   
        }   
              
        return ++last;
    } 
}

Time complexity is O(n), space complexity is O(1)

Remove Duplicates from Sorted Array II