问题：

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.

 

官方难度：

Easy

 

翻译：

给定一个已经排序的数组，删除重复元素，返回新数组的长度。程序不关心这个长度之后存储的是什么东西。

 

例子：

给定数组：[1,1,2]

返回长度：2，且数组以[1,2]开头。

 

1. 有2个很关键的信息：数组有序，不关心长度之后的内容。
2. 不关心长度之后的内容，题目暗示了，在原数组上处理数据的内容。
3. 由于数组有序，维护一个快指针（从第2项开始），一个慢指针（从第1项开始）。快指针遍历数组，判断两个指针指向的数字是否相同。若相同，不做处理；若不同，慢指针向前移一位，且快指针的值覆盖慢指针的值。
4. 结束循环，返回长度为慢指针+1。
5. 入参检查，同时，长度小于2的直接返回。

 

解题代码：

1     public static int removeDuplicates(int[] array) { 2         if (array == null) { 3             throw new IllegalArgumentException("Input error"); 4         } 5         if (array.length < 2) { 6             return array.length; 7         } 8         // 慢指针 9         int i = 0;10         for (int j = 1; j < array.length; j++) {11             // 快指针不断前进，遇到与慢指针数字相同的情况，跳过12             if (array[j] != array[i]) {13                 i++;14                 array[i] = array[j];15             }16         }17         // 返回新数组的长度，不关心之后的内容18         return i + 1;19     }

 

相关链接：

 

PS：如有不正确或提高效率的方法，欢迎留言，谢谢！