Java题刷刷本文讲解三道经典的双指针/三指针 可以是刷题启蒙 作为算法的复习也非常美味1.删除有序数组中的重复项题目链接:26. 删除有序数组中的重复项 - 力扣LeetCode题目描述给你一个非严格递增排列的数组nums请你** 原地** 删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回nums中唯一元素的个数。考虑nums的唯一元素的数量为k。去重后返回唯一元素的数量k。nums的前k个元素应包含排序后的唯一数字。下标k - 1之后的剩余元素可以忽略。输入nums [3,2,2,3], val 3 输出2, nums [2,2,_,_]输入nums [0,1,2,2,3,0,4,2], val 2 输出5, nums [0,1,4,0,3,_,_,_]算法/思路我们从样例看出来 这里是伪删除方法一 复制法这个方法很容易想到 可以通过这道题 但是时间和空间都花了比较多 也没有做到原地遍历nums数组 使用set也不一定得是红黑树 哈希表也可以来处理只出现一次这个条件 我们搞个新数组arr用来存放只出现一次的数据 最后把arr内容按序赋值给nums数组就行了方法二 双指针法方法一我们似乎没有用到非严格递增排列这个条件 我们观察到如果当前遍历的数和前一个不一样那么它肯定是第一个这个数值的第一次出现所以我们可以把前面有重复的 用这个数值来覆盖所以我们就想到用两个指针来指向这个数组编写代码方法一classSolution{publicintremoveDuplicates(int[]nums){// 对0进行特殊处理(也可以不用)if(nums.length0)return0;// 利用set的特性 哈希表也是可以的TreeSetIntegersetnewTreeSet();int[]arrnewint[nums.length];intj0;for(intnum:nums){if(!set.contains(num)){// 主要就是为了这个// 只出现一次的数值存放进去set和arrset.add(num);arr[j]num;}}// 把arr的数据赋值给numsfor(inti0;ij;i){nums[i]arr[i];}// j既是arr的长度也是删除之后的nums数组的长度returnj;}}方法二classSolution{publicintremoveDuplicates(int[]nums){intlennums.length;// 对0特殊处理if(len0){return0;}// 定义另一个指针 又因为第一个元素一定不重复所以一定保留intm1;for(inti1;ilen;i){if(nums[i]!nums[m-1]){// -1 是因为数组是0下标开始的嘛nums[m]nums[i];// m 别忘了}}returnm;}}2.移除元素题目链接:27. 移除元素 - 力扣LeetCode题目描述给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。假设nums中不等于val的元素数量为k要通过此题您需要执行以下操作更改nums数组使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。返回k。输入nums [3,2,2,3], val 3 输出2, nums [2,2,_,_]输入nums [0,1,2,2,3,0,4,2], val 2 输出5, nums [0,1,4,0,3,_,_,_]算法原理我们需要把非删除元素移动到左边要删除的直接被不删除的覆盖掉就好了 受到上一题的启发我们在定义一个指针指向要删除的元素 一但被覆盖就往右边移动 需要注意的是 要被不想删除的值覆盖 即nums[i] !val这种情况再覆盖编写代码classSolution{publicintremoveElement(int[]nums,intval){intlennums.length;// 指向要删除的元素intj0;for(inti0;ilen;i){if(nums[i]!val){nums[j]nums[i];// 覆盖掉 后面不用关了}}returnj;}}3.合并两个有序数组题目链接:88. 合并两个有序数组 - 力扣LeetCode题目描述给你两个按非递减顺序排列的整数数组nums1和nums2另有两个整数m和n分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中使合并后的数组同样按非递减顺序排列。注意最终合并后数组不应由函数返回而是存储在数组nums1中。为了应对这种情况nums1的初始长度为m n其中前m个元素表示应合并的元素后n个元素为0应忽略。nums2的长度为n。输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3 输出[1,2,2,3,5,6]输入nums1 [1], m 1, nums2 [], n 0 输出[1]输入nums1 [0], m 0, nums2 [1], n 1 输出[1]算法原理方法一我们利用好非递减这个条件 题目还说了第一个数组的长度是完全塞得下第二个数组的 我们反着来定义两个指针分别指向两个数组有效数据的最后 再定义一个指针指向num1假长度的最后的指针pnums1[p1]和nums2[p2]两者进行比较大小 大的直接赋值给nums1[p]然后数值被使用的指针就往前移动 另一个不变 但是有一些问题 注意到如果p1先到-1 说明nums1原来的有效元素全部被移到了后面 而nums2还剩一些较小的数没放进去 这些数应该放到nums1前面的空位上 所以需要第二个while循环把它们拷过去方法二因为是有序的合并 所以很容易想到使用自带的排序方法没什么好说的 但是提交的时候发现比方法一是慢挺多编写代码方法一:classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){intp1m-1;// 指向nums1[]intp2n-1;// 指向nums2[]intpmn-1;while(p10p20){if(nums1[p1]nums2[p2]){nums1[p--]nums1[p1--];}else{nums1[p--]nums2[p2--];}}// 如果 p1 先 0 的情况下 把 num2 剩余的拷过去while(p20){nums1[p--]nums2[p2--];}}}方法二classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){System.arraycopy(nums2,0,nums1,m,n);Arrays.sort(nums1);}}✍️ 写在最后如有问题或建议或更优的做法欢迎在评论区留言交流或直接私信
【Java算法竞赛】双/多指针算法 竟然这么简单
Java题刷刷本文讲解三道经典的双指针/三指针 可以是刷题启蒙 作为算法的复习也非常美味1.删除有序数组中的重复项题目链接:26. 删除有序数组中的重复项 - 力扣LeetCode题目描述给你一个非严格递增排列的数组nums请你** 原地** 删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回nums中唯一元素的个数。考虑nums的唯一元素的数量为k。去重后返回唯一元素的数量k。nums的前k个元素应包含排序后的唯一数字。下标k - 1之后的剩余元素可以忽略。输入nums [3,2,2,3], val 3 输出2, nums [2,2,_,_]输入nums [0,1,2,2,3,0,4,2], val 2 输出5, nums [0,1,4,0,3,_,_,_]算法/思路我们从样例看出来 这里是伪删除方法一 复制法这个方法很容易想到 可以通过这道题 但是时间和空间都花了比较多 也没有做到原地遍历nums数组 使用set也不一定得是红黑树 哈希表也可以来处理只出现一次这个条件 我们搞个新数组arr用来存放只出现一次的数据 最后把arr内容按序赋值给nums数组就行了方法二 双指针法方法一我们似乎没有用到非严格递增排列这个条件 我们观察到如果当前遍历的数和前一个不一样那么它肯定是第一个这个数值的第一次出现所以我们可以把前面有重复的 用这个数值来覆盖所以我们就想到用两个指针来指向这个数组编写代码方法一classSolution{publicintremoveDuplicates(int[]nums){// 对0进行特殊处理(也可以不用)if(nums.length0)return0;// 利用set的特性 哈希表也是可以的TreeSetIntegersetnewTreeSet();int[]arrnewint[nums.length];intj0;for(intnum:nums){if(!set.contains(num)){// 主要就是为了这个// 只出现一次的数值存放进去set和arrset.add(num);arr[j]num;}}// 把arr的数据赋值给numsfor(inti0;ij;i){nums[i]arr[i];}// j既是arr的长度也是删除之后的nums数组的长度returnj;}}方法二classSolution{publicintremoveDuplicates(int[]nums){intlennums.length;// 对0特殊处理if(len0){return0;}// 定义另一个指针 又因为第一个元素一定不重复所以一定保留intm1;for(inti1;ilen;i){if(nums[i]!nums[m-1]){// -1 是因为数组是0下标开始的嘛nums[m]nums[i];// m 别忘了}}returnm;}}2.移除元素题目链接:27. 移除元素 - 力扣LeetCode题目描述给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。假设nums中不等于val的元素数量为k要通过此题您需要执行以下操作更改nums数组使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。返回k。输入nums [3,2,2,3], val 3 输出2, nums [2,2,_,_]输入nums [0,1,2,2,3,0,4,2], val 2 输出5, nums [0,1,4,0,3,_,_,_]算法原理我们需要把非删除元素移动到左边要删除的直接被不删除的覆盖掉就好了 受到上一题的启发我们在定义一个指针指向要删除的元素 一但被覆盖就往右边移动 需要注意的是 要被不想删除的值覆盖 即nums[i] !val这种情况再覆盖编写代码classSolution{publicintremoveElement(int[]nums,intval){intlennums.length;// 指向要删除的元素intj0;for(inti0;ilen;i){if(nums[i]!val){nums[j]nums[i];// 覆盖掉 后面不用关了}}returnj;}}3.合并两个有序数组题目链接:88. 合并两个有序数组 - 力扣LeetCode题目描述给你两个按非递减顺序排列的整数数组nums1和nums2另有两个整数m和n分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中使合并后的数组同样按非递减顺序排列。注意最终合并后数组不应由函数返回而是存储在数组nums1中。为了应对这种情况nums1的初始长度为m n其中前m个元素表示应合并的元素后n个元素为0应忽略。nums2的长度为n。输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3 输出[1,2,2,3,5,6]输入nums1 [1], m 1, nums2 [], n 0 输出[1]输入nums1 [0], m 0, nums2 [1], n 1 输出[1]算法原理方法一我们利用好非递减这个条件 题目还说了第一个数组的长度是完全塞得下第二个数组的 我们反着来定义两个指针分别指向两个数组有效数据的最后 再定义一个指针指向num1假长度的最后的指针pnums1[p1]和nums2[p2]两者进行比较大小 大的直接赋值给nums1[p]然后数值被使用的指针就往前移动 另一个不变 但是有一些问题 注意到如果p1先到-1 说明nums1原来的有效元素全部被移到了后面 而nums2还剩一些较小的数没放进去 这些数应该放到nums1前面的空位上 所以需要第二个while循环把它们拷过去方法二因为是有序的合并 所以很容易想到使用自带的排序方法没什么好说的 但是提交的时候发现比方法一是慢挺多编写代码方法一:classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){intp1m-1;// 指向nums1[]intp2n-1;// 指向nums2[]intpmn-1;while(p10p20){if(nums1[p1]nums2[p2]){nums1[p--]nums1[p1--];}else{nums1[p--]nums2[p2--];}}// 如果 p1 先 0 的情况下 把 num2 剩余的拷过去while(p20){nums1[p--]nums2[p2--];}}}方法二classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){System.arraycopy(nums2,0,nums1,m,n);Arrays.sort(nums1);}}✍️ 写在最后如有问题或建议或更优的做法欢迎在评论区留言交流或直接私信
