26.从排序数组中删除重复项
容易的
给定一个排序的数组nums，就地移除重复的，使得每个元素只出现一次，并返回新的长度。
不要为另一个数组分配额外的空间，必须通过用O(1)额外的内存就地修改输入数组来实现。
澄清:
困惑为什么返回值是整数而你的答案是数组？
注意，输入数组是通过引用传入的，这意味着对输入数组的修改也将被调用者所知。
在内部，你可以这样想:
// nums is passed in by reference. (i.e., without ***king 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]);}
例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 ***tter what you leave beyond the returned length.
例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 ***tter what values are set beyond the returned length.
约束:
0 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums 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次遍历来解决问题。
此外，它不占用额外的空空间，只能创建一个新指针和当前给定的数组进行操作。
本文来自润情无声投稿，不代表舒华文档立场，如若转载，请注明出处：https://www.chinashuhua.cn/24/480753.html
微信扫一扫 
