[leetcode] Remove Duplicates From Sorted Array | 排好序的数组inplace的remove dup，不用额外空间

Posted by: lexigrey on: October 11, 2013

• In: leetcode
• Leave a Comment

这题八月轻松过，现在十月看看就彻底不会了。感觉跟array有关的自己想算法的题就能把我吓个好歹。多做多总结！

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

Your function should return length = 2, and A is now [1,2,1].（length之后的都不管了）。

算法：

1. i从1开始，遇见和上一个不一样的，就放在j指的位置里，j++
2. 要是arr[i] == arr[i – 1]，i继续往后走

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

Tags: array, 一快一慢双指针