LeetCode 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 nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

 

 

---

题目标签：Array 　　这道题目给了我们一个有序array， 让我们把重复的都移除，并且要求我们不能利用额外的空间，只能在原有的array里改。这里需要两个pointers， i 和 j。 设置j 为0， i 从1 开始遍历。目的是让i 找到一个不重复的数字，一旦找到，我们把这个数字放在j 的后面一个位子。这样的话，所有重复的数字，都会放在j后面。j之前的包括j的部分都是不重复的。最后只要return j+1 就可以了。    

Java Solution:

Runtime beats 55.60% 

完成日期：03/09/2017

关键词：Array

关键点：利用two pointers

 

public class Solution 
{
    public int removeDuplicates(int[] nums) 
    {
        // check validation.
        if(nums.length == 0)
            return 0;
        
        
        int j = 0;
        
        // iterate nums array.
        for(int i=1; i<nums.length; i++)
        {
            // once find the nums[i] that doesn't match nums[j]
            if(nums[i] != nums[j])
            {
                j++;
                // swap the non-duplicate one with duplicate one or with itself
                nums[j] = nums[i];
            }
            
        }
        
        return j+1;
    }
}

参考资料：N/A

 

LeetCode 算法题目列表 - LeetCode Algorithms Questions List