长安商城网站建设,微信公众号运营方法,跨境电商运营基础知识,企业网站建站技术使用双指针来解决此问题#xff0c;关键词“有序”数组#xff0c;一个 index 指针用于构建新数组#xff0c;一个 i 指针用于遍历整个数组
以下是代码的中文解释以及算法思想#xff1a;
算法思想
这道题要求对一个有序数组进行去重#xff0c;使得每个元素最多出现两…
使用双指针来解决此问题关键词“有序”数组一个 index 指针用于构建新数组一个 i 指针用于遍历整个数组
以下是代码的中文解释以及算法思想
算法思想
这道题要求对一个有序数组进行去重使得每个元素最多出现两次。我们需要在原数组上进行操作不能使用额外的空间。为了实现这个要求我们可以使用双指针法来完成 初始化两个指针 index 指针表示下一个可以插入的有效位置用于构建结果数组它初始值为 2因为前两个元素无论如何都可以直接保留。i 指针遍历整个数组从第三个元素开始检查因为我们允许每个元素最多出现两次所以不需要检查前两个元素。 条件检查 对于每个元素 nums[i]我们检查它是否等于 nums[index - 2]。如果不等则表示 nums[i] 至少可以插入到当前构建的结果数组中。如果 nums[i] ! nums[index - 2]则将 nums[i] 放到 nums[index] 位置上并将 index 指针向后移动一位准备下一个位置。 返回结果 最终 index 的值就是新数组的长度因为 index 指针的值代表了有效数组的长度。原数组前 index 个元素就是去重后的数组且每个元素最多出现两次。
代码示例
public class Solution {public int removeDuplicates(int[] nums) {if (nums.length 2) return nums.length;int index 2; // 从第三个元素开始检查for (int i 2; i nums.length; i) {// 如果当前元素 nums[i] 不等于 nums[index - 2]说明该元素可以加入if (nums[i] ! nums[index - 2]) {nums[index] nums[i];index;}}return index;}
}具体解释
数组长度小于等于 2如果数组长度不超过 2直接返回数组长度因为每个元素都可以出现两次。遍历数组 从第三个元素开始i 2逐个检查每个元素 nums[i]。如果当前元素 nums[i] 不等于 nums[index - 2]表示当前元素没有超过出现两次的限制。将当前元素 nums[i] 放到 nums[index] 位置上然后将 index 向后移动一位。 返回结果index 的值就是数组去重后的长度数组的前 index 个元素就是符合要求的结果。
复杂度分析
时间复杂度O(n)因为我们只遍历了一遍数组。空间复杂度O(1)因为我们在原数组上进行操作没有使用额外的空间。
示例
假设输入数组为 {1, 1, 1, 2, 2, 3}
初始状态index 2遍历 i 2nums[i] 1nums[index - 2] 1相等跳过此元素。i 3nums[i] 2nums[index - 2] 1不相等将 nums[i] 赋值给 nums[index]index 增加 1。i 4nums[i] 2nums[index - 2] 1不相等将 nums[i] 赋值给 nums[index]index 增加 1。i 5nums[i] 3nums[index - 2] 2不相等将 nums[i] 赋值给 nums[index]index 增加 1。 最终结果返回的长度 index 5即 {1, 1, 2, 2, 3}
java 代码如下
class Solution {public int removeDuplicates(int[] nums) {// if (nums.length 2) return nums.length;int index 2;for(int i 2; i nums.length; i) {if(nums[i] ! nums[index - 2]) { //注意是index - 2, 而不是 i - 2nums[index] nums[i];}}return index;}
}为什么这行代码的判断条件不是nums[i] ! nums[i - 2]
if (nums[i] ! nums[index - 2]) {这是一个很好的问题。之所以判断条件写成 nums[i] ! nums[index - 2] 而不是 nums[i] ! nums[i - 2]是因为我们希望使用 index 指针来追踪构建新数组的有效长度并确保每个元素最多出现两次。下面是具体原因
原因解释 index 指针的作用 index 指针代表的是新数组的当前位置也就是我们构建的、符合条件的数组的长度。index - 2 始终指向新数组的倒数第二个元素。因此nums[index - 2] 可以用来判断当前的 nums[i] 是否已经出现了两次。 避免原数组的重复元素影响判断 如果直接用 nums[i - 2]它表示的是原数组的倒数第二个元素。然而我们的目标是构建一个新的符合条件的数组这个数组并不直接等同于原数组。例如在原数组中某个元素可能已经出现多次但在新数组由 index 控制中它可能只出现了一次。因此判断条件需要使用 nums[index - 2] 而不是 nums[i - 2]。 控制新数组的内容 通过 nums[index - 2]我们可以确保只有符合条件的元素才被添加到新数组中避免出现超过两次的重复。如果使用 nums[i - 2]则我们判断的是原数组中的元素而不是新构建的数组可能会导致多次重复的元素被错误地加入。
举例说明
假设输入数组为 {1, 1, 1, 2, 2, 3} 初始时 index 2我们从第三个元素i 2开始遍历。 当 i 2 时nums[i] 1如果我们使用 nums[i - 2] 进行判断那就是 nums[0] 1。此时它会与 nums[i] 相等判断条件为 false意味着它会被加入到新数组中导致 1 出现三次这是不符合题意的。而使用 nums[index - 2]即 nums[0] 1作为判断条件时我们可以正确地跳过这个元素避免多余的重复。
通过使用 index 指针我们有效地控制了新数组的内容并保证每个元素最多出现两次。
