26. Remove Duplicates from Sorted Array
Easy
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: 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 returned length.
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: Your function should return length = 5
, with the first five elements of nums
being modified to 0
, 1
, 2
, 3
, and 4 respectively. It doesn\'t matter what values are set beyond the returned length.
Constraints:
- 0 <= nums.length <= 3 * 104
- -104 <= nums[i] <= 104
- nums is sorted in ascending order.
给定一个有序数组，删除重复内容，使每个元素只出现一次，并返回新的长度。
题目要求不要为其他数组分配额外的空间，您必须通过在 O（1）额外的内存中就地修改输入数组来实现这一点。
解题思路：
这是一道难度简单的题目，已知条件数组是已排序的，且不能新建数组，这就是告诉我们除了创建数组指针只能改变给定数组来得到结果。
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0; //首先排除边界的case
}
int counter = 0, i = 1; //定义两个指针，counter代表当前去重的长度，i是遍历的指针，为什么i是从1开始？ 因为起始位置的数组元素已经计算到结果中，所以开始从二个元素遍历
while(i < n) {
if (nums[counter] == nums[i]) { //判断当前遍历的数组元素和去重后的最大数组元素是否相同，如果相同则继续遍历，不做任何操作。
i++;
} else { //如果不同，则将数组当前遍历的元素替换到去重数组
counter++; //在替换前首先将去重指针后移一位
nums[counter] = nums[i];
i++; //继续遍历
}
}
return counter + 1; //counter是去重指针的最后一位，所以长度需要加1
}
}总结：这类数组去重的题会经常出现在面试环节中（3sum），看到数组去重我们就要想到对数组先进行排序，然后通过一个n的遍历就能解决问题。
另外就是不占用额外空间，只能新建指针和当前给定的数组来操作。
