26. Remove Duplicates from Sorted Array

题目：

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.

For example,
Given input array A = [1,1,2],

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

链接： http://leetcode.com/problems/remove-duplicates-from-sorted-array/

题解：

从数组中移除重复值。Time Complexity - O(n)，Space Complexity - O(1)

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        int count = 1;
for(int i = 1; i < A.length; i++)
            if(A[i] != A[i - 1])
                A[count++] = A[i];
return count;
    }
}

 

二刷： 

第一个元素不判断，从第二个元素开始遍历，遇到不相同的，则增加index。

Java:

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

 

三刷:

这道题跟27很像，关键是判断出我们不考虑第一个元素，从第二个元素开始遍历，而且一开始的index也是设置为1. 条件是当nums[i] != nums[i - 1]的时候，我们更新nums[index++] = nums[i]。

Java:

Time Complexity - O(n)，Space Complexity - O(1)

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