国外知名设计网站大全,公司营销型网站制作,漯河市郾城区网站建设,创业网站建设政策移除元素
今日的题目依旧是力扣面试经典算法150题中数组相关的题目#xff1a;移除元素 题目链接#xff1a;https://leetcode.cn/problems/remove-element/description/?envTypestudy-plan-v2envIdtop-interview-150 题目描述
给定一个排序数组 nums 和一个值 val移除元素 题目链接https://leetcode.cn/problems/remove-element/description/?envTypestudy-plan-v2envIdtop-interview-150 题目描述
给定一个排序数组 nums 和一个值 val需要在原地移除数组中所有等于val 的元素并返回移除后数组的新长度。不需要考虑超出新长度以外的元素。
注意: 必须在原地修改输入数组不能使用额外的数组空间。元素的顺序可以改变你不需要考虑数组中超出新长度后面的元素。 示例: 输入: nums [3,2,2,3], val 3输出: 新长度为 2数组变为 [2,2]注意返回值为新长度数组内容可以不是连续的 解释: 数组 nums 中的值 3 被移除了两次。移除后的新数组长度为 2数组内容为 [2,2]。
题目分析
题目要求我们在不使用额外空间的情况下移除数组中的特定元素并返回移除后的数组长度。
为了达到 O(1) 的额外空间复杂度这要求我们需要在原地修改数组。
解题思路
题目的要求就两个一个移出元素一个将不同的元素放到原本的数组中。这就意味着我们需要在一个循环中进行两种操作这里很容易就会想到用双指针来完成一个指针拿出元素比较一个指针将元素放入数组并且这个指针最后停留的下标就是最后一个不同的元素。
实际算法代码
根据以上分析和思路我们可以写出以下代码
import java.util.Arrays;/*** description** author 明月望秋思* date 2024/8/6 */
public class RemoveElement {/*** 移除数组中的指定元素** param nums 输入数组* param val 需要移除的值* return 移除后的新数组长度*/public int removeElement(int[] nums, int val) {// 指针1,用于遍历数组比较元素int i 0;// 指针2,用于记录新数组的下标位置int j 0;// 遍历数组while (i nums.length) {// 比较元素是否与val相等if (nums[i] ! val) {nums[j] nums[i];// 只有元素不同时才放入元素并更新指针2j; }// 更新指针1不管元素是否相同都要向下遍历i; }// 返回新数组的长度,因为在循环中进行了的操作return j; public static void main(String[] args) {RemoveElement solution new RemoveElement();// 示例数据int[] nums {3, 2, 2, 3};int val 3;// 调用移除方法int newLength solution.removeElement(nums, val);// 输出新长度和移除后的数组System.out.println(New length: newLength);System.out.println(Modified array: Arrays.toString(Arrays.copyOfRange(nums, 0, newLength)));}
}提交代码测试通过。 因为算法用到了双指针下面讲一下双指针法的内容。
双指针法
双指针法是一种常用的算法技巧它通过使用两个指针来遍历数据结构如数组或链表以简化问题的解决过程。
使用场景
双指针法适用于多种场景下面列举了一些常见的使用双指针法的场景及其原因
在原数组对象操作数组 场景描述不增加额外空间复杂度度的情况下完成对数组的操作。原因双指针法可以直接在原数组上进行操作可以减少不必要的比较和浪费额外的空间。 寻找两个数使它们的和为特定值 场景描述给定一个有序数组找到数组中两个数使它们的和等于特定的目标值。原因有序数组允许我们使用双指针从两端向中间逼近一个指针从头部开始另一个从尾部开始。这样可以避免不必要的比较提高效率。 快速排序中的分区操作 场景描述在快速排序算法中需要选择一个基准值并将小于基准值的元素放在左边大于基准值的元素放在右边。原因双指针可以帮助我们有效地进行分区操作一个指针从左向右移动另一个从右向左移动当两个指针指向的元素不符合分区规则时交换它们的位置。 求解回文子串 场景描述给定一个字符串判断它是否是回文串或者找出最长的回文子串。原因对于回文串中心对称的特性使得我们可以使用双指针从中心向两边扩展来检查字符串是否为回文。 求解链表的中间节点 场景描述给定一个单链表需要找到链表的中间节点。原因使用快慢指针快指针每次移动两步慢指针每次移动一步当快指针到达链表尾部时慢指针正好位于中间。 反转链表 场景描述给定一个链表需要反转链表的顺序。原因使用双指针技巧一个指针指向当前节点另一个指针指向当前节点的前一个节点通过调整指针方向来实现反转。 滑动窗口 场景描述在数组或字符串中找到满足特定条件的最大或最小子序列。原因双指针可以用来定义滑动窗口的边界一个指针作为窗口的起始位置另一个指针作为窗口的结束位置随着遍历动态调整窗口大小以满足条件。 寻找重复元素 场景描述在有序数组中查找重复元素。原因使用双指针技巧一个指针从头开始另一个指针从尾开始根据元素的大小关系移动指针来寻找重复项。 合并两个有序数组 场景描述给定两个有序数组需要将它们合并成一个新的有序数组。原因使用双指针从后向前比较两个数组的元素并将较大的元素放入结果数组的末尾可以保证合并后的数组仍然是有序的。 检测链表中的环 场景描述给定一个链表需要检测链表中是否存在环。原因使用快慢指针技巧快指针每次移动两步慢指针每次移动一步如果存在环快指针最终会追上慢指针。
双指针法之所以在这些场景中有效是因为它能够减少不必要的比较次数提高算法的时间效率并且在很多情况下能够避免使用额外的空间从而达到 O(1) 的空间复杂度。
双指针法的优点
双指针法有以下优点
原地修改不需要额外的空间来存储新数组直接在原数组上进行修改这样就可以在 O(1) 的额外空间复杂度下完成移除操作。保持有序性在移除元素的过程中可以使有效元素仍然保持有序。效率高只需要遍历一次数组即可完成移除操作时间复杂度为 O(n)。简单易实现双指针法的逻辑简单易于理解和实现
总结
实际上上一篇文章中的题目也是用的双指针法。
双指针法在处理数组的算法题时是比较常见且又好用的一种解决办法。
熟练使用可以更好的帮助在数组方面的问题
