陕西手机网站建设公司排名,获取网页 代码 做网站,程序开发用什么笔记本,整套网站设计删除排序数组中的重复项 II题目给定一个增序排列数组 nums #xff0c;你需要在 原地 删除重复出现的元素#xff0c;使得每个元素最多出现两次#xff0c;返回移除后数组的新长度。不要使用额外的数组空间#xff0c;你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的… 删除排序数组中的重复项 II题目给定一个增序排列数组 nums 你需要在 原地 删除重复出现的元素使得每个元素最多出现两次返回移除后数组的新长度。不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。(来源LeetCode 80)例子示例1输入nums [1,1,1,2,2,3]输出5, nums [1,1,2,2,3]示例2输入nums [0,0,1,1,1,1,2,3,3]输出7, nums [0,0,1,1,2,3,3]示例3输入nums [1,1,1,1]输出2, nums [1,1]解题思路这道题目其实是前面我们有聊过的“删除排序数组中的重复项“的进阶版其实我们直接的思路大体相似无非这道题目是使每个元素最多出现两次当然代码实现上会稍微复杂一些注意的条件也比较多。思路一我们还是遍历数组我们可以从第三个元素开始遍历当nums[i]nums[i-2]时即这三个元素完全相等时我们可以往后面找找到一个和nums[i]不相同的元素为止将这后面这一串往前挪这里就要注意不同情况当往后找的过程中如果找不到那就应该直接返回i例如nums[1,1,1,1,1];如果找到了我们移动的的时候也要注意我们先定义个变量标记移动了多少位然后进行赋值赋值完后“数组的长度”其实也是分两种情况的例如nums[1,1,1,1,1,2,3,4,5],我们移动后变成nums{1,1,2,3,4,5,3,4,5},但是我们应该只取前6位例如nums{1,1,1,1,1,2},我们移动后变成nums{1,1,2,1,1,2},但是我们应该只取前2位这就是两只不同情况具体大家可以结合下面图示和代码仔细揣摩一下。所以我们移动完后要改变遍历的数组长度直至遍历结束i就是需要返回的数组长度。思路二上述我们其实貌似不用这么复杂我们定义两个指针n,i一个负责往后遍历一个记录当前“新数组“需要存放的最新位置当往后遍历的过程中发现当索引下标的值不等于前面第二个元素时则将数组记录需要存放的最新位置设置成当前元素,以此类推返回i即为数组长度大家可以结合如下代码仔细思考一下再尝试着自己去实现。删除排序数组中的重复项MR.Zhu公众号1024和996删除排序数组中的重复项代码实现/** * leetcode 80 */public class Solution { /** * 方法一 * * param nums * return */ public int removeDuplicates(int[] nums) { if (nums null || nums.length 0) { return 0; } if (nums.length 3) { return nums.length; } int i 2; int length nums.length; while (i length) { if (nums[i] nums[i - 2]) { int flag i; int point i; while (point 1 ! length nums[point] nums[point 1]) { point; } //没找到则返回 if (point 1 length) { return i; } //移动赋值 for (int j point 1, k 0; j length; j, k) { nums[flag k] nums[j]; } //判断有效长度 if (length - point - 1 point - i) { length i (length - point - 1); } else { length length - (point 1 - i); } } i; } return i; } /** * 方法二 * param nums * return */ public int removeDuplicates2(int[] nums) { int i0; for(int n:nums){ if(i2){ i; continue; } if(n!nums[i-2]){ nums[i]n; i; } } return i; } public static void printArr(int[] arr) { for (int num : arr) { System.out.print(num \t); } System.out.println(); } public static void main(String[] args) { int nums[] { 0, 1, 1, 1, 1, 2, 3, 3, 3, 4 }; System.out.println(方法一删除重复项后数组长度: new Solution().removeDuplicates(nums)); System.out.println(方法一删除重复项后数组为:); printArr(nums); int nums2[] { 0, 1, 1, 1, 1, 2, 3, 3, 3, 4 }; System.out.println(方法二删除重复项后数组长度: new Solution().removeDuplicates2(nums2)); System.out.println(方法二删除重复项后数组为:); printArr(nums2); }}运行结果
