当前位置：首页 > news >正文

《算法通关村——双指针妙用》

news 2025/9/15 6:19:23

《算法通关村——双指针妙用》

删除元素

描述

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。要求：不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

例子1: 输入：nums = [3,2,2,3], val = 3 
输出：2, nums = [2,2] 
例子2： 输入：nums = [0,1,2,2,3,0,4,2], val = 2 
输出：5, nums = [0,1,4,0,3]

三种解决方法解决

/*** 删除指定元素用快慢指针,慢指针用于填充不删除的值，快指针用于查找目标值* @param nums* @param val* @return*/
public static  int removeElement(int[] nums,int val){int slow = 0;// fast充当快指针for(int fast = 0;fast<nums.length;fast++){if(nums[fast] != val){nums[slow] = nums[fast];slow++;}}return slow;
}/*** 对撞指针的方法，两个指针从两边走，左边如果不相等（不等于目标值）就往后，right等于目标值就往前。* @param nums* @param val* @return*/
public static int removeElement1(int[] nums,int val){int right = nums.length-1;int left = 0;while(left <= right){if((nums[left]==val) && (nums[right]!= val)){int temp = nums[right];nums[right] = nums[left];nums[left] = temp;}if(nums[left] != val)  left++;if(nums[right]==val) right--;}return left;
}/*** 双指针＋覆盖，这种就是直接覆盖了，如果从左开始有值等于目标值，就把他替换成从右边开始的值，然后右边指针移动，左边不动，* 然后再次判断左边原位置是否是目标值，如果是就继续覆盖，右边指针继续移动，如果不是左边指针移动。* @param nums* @param val* @return*/
public static int removeElement2(int[] nums, int val){int right = nums.length - 1;for(int left = 0; left<=right;){if(nums[left] == val){nums[left] = nums[right];right--;}else{left++;}}return right+1;
}

删除重复项

描述

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例1： 
输入：nums = [1,1,2] 
输出：2, nums = [1,2] 
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。  
例子2： 
输入：nums = [0,0,1,1,1,2,2,3,3,4] 
输出：5, nums = [0,1,2,3,4] 
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

解决

/*** 删除数组中重复元素，返回数组的大小。慢指针进行存值覆盖，快指针判断是否为重复值。* @param nums* @return*/
public static int removeDuplicates(int[] nums){// slow表示可以放入新元素位置，索引为0的元素不用管.int slow = 1;// 循环起到了快指针的作用for(int fast = 0;fast < nums.length;fast++){if(nums[fast] != nums[slow-1]){nums[slow] = nums[fast];slow++;}}return slow;
}