【LeetCode】原地移除元素、删除排序数组中的重复项

时间：2024-11-02 12:11:04

主页：HABUO????主页：HABUO 

1.原地移除元素

题目：给你一个数组 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,_,_]    解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

输入：nums = [0,1,2,2,3,0,4,2], val = 2   输出：5, nums = [0,1,4,0,3,_,_,_]   解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

分析：根据前面顺序表实现的一个思想，我们要消除数组当中等于val的值，最简单的思想是不是就是，我们去遍历这数组遇到这个值，把它删去，然后把后面的数据往前移，但这个思想也很容易想到它的时间复杂度是不是O(N^2),不太好，或者我们可以这样做建立一个数组，遍历原来的数组，遇到不等于val的数据把它放到新的数组上，这样我们遍历一遍数组就可以实现时间复杂度是O(N),这样就不错，但是题中是说原地移除，不让我们建立新的数组，怎么办？我们可以这样做，创建两个标签指向这段数组，遇到不等于val值的数据两个标签同时移动，遇到等于的一个继续移另一个不动，直到移动的标签到不等于val值的数据停止，把移动的数据传给之前不动的标签处，这就实现了，就类比了创建一个新数组，把不等于的放置在新数组上。整体思路见下图：

需要注意：当right遇到不等于val的值时，left与right共同往前，把right赋值给left需在这之前进行。代码实现见下：

int removeElement(int* nums, int numsSize, int val)
{
    int left = 0;
    for (int right = 0; right < numsSize; right++) 
    {
        if (nums[right] != val) {
            nums[left] = nums[right];
            left++;
        }
    }
    return left;
}

2.删除排序数组中的重复项

题目：给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

示例：

输入：nums = [1,1,2]    输出：2, nums = [1,2,_]    解释：函数应该返回新的长度2，并且原数组 nums 的前两个元素被修改为1，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。不需要考虑数组中超出新长度后面的元素。

分析：得益于上一题的思考，我们仍然可以采用两个指针指向，进行解决，定义两个指针left、right，大体思路就是right==left，right往前走，直到right != left我们就让right赋值给left，然后right和left都往前走一步，这就是思想，但是这个过程如果思维不缜密会出现许多的问题，见下文如何分析：

第一个问题：这里有很多问题需要注意：比如第一个元素我们怎么解决，它肯定是要被留下来的，然后我们让right与left都往前走了一步，此时第二个元素与第一个相等还好，如果不等呢？我们让right往后走遇到与left不等的把值赋给它可是第二个元素也应该被留下来，此时我们就丢失了数据，如下图所示：

第二个问题：如果在数组中连续放着多个相同元素的话，right往前走到和left不相等的时候把值赋给了left，但是right下一个的值如果与上一个值相等而left下一个值和上一个也相等，但是right和left仍然不相等，它还会把值赋给left，这就完了，我们好不容易去的重，它重现把重复的值重复的赋，这就污染了我们前面的工作。具体见下图：

解决方法：第一个问题：我们可以将right与left进行错开，如果不等呢，就将right和left同时向前一步，如果相等呢就把right往前一步，这样就顺利的把第二个元素保留了下来，但就因为这个举动，后面的文章就相对繁琐，因为如果咱们的数据都不想等，相当于left走在了前面，最终我们要防止越界，就要去控制left，但如果之间有相等的我们就需要控制right来防止越界，这就把简单的问题复杂化了，所以我们从一开始就走错了，不应该把right和left错开，虽然这样可以实现，悄悄告诉你我就是这样实现的????，最终在逐渐的分析调试中走完了整个程序，花费了巨大时间????，所以我们回到开头，数据在数组当中存放，我们指针往前走的过程中，前一个数据是仍然可以访问的嘛，这一点我们不应该忘记所以我们就去判断right和right-1不就行了，这就很好。第二个问题：我们很直接的想法是因为left下一个值是和上一个值相等导致了这个问题，那我们可不可以把下一个值和当前应该修改的值一并修改成如上图所示的4呢？当然可以，我就是这样想的????，其实呢，如果第一个问题我们采用第二种解法的话，这个问题也就迎刃而解了，具体见下面实现：

int right = 1, left = 1;
if (nums[right] != nums[right - 1])
{
    nums[left] = nums[right];
    ++left;
}
++right;

用上面的方法解决呢，最终我们只需要控制right别越界即可，这就把问题简单化了，整体代码见下：

int removeDuplicates(int* nums, int numsSize) 
{
    if (numsSize == 0) 
    {
        return 0;
    }
    int right = 1, left = 1;
    while (right < numsSize) 
    {
        if (nums[right] != nums[right - 1])
        {
            nums[left] = nums[right];
            ++left;
        }
        ++right;
    }
    return left;
}

总结（知识领悟）：

（1） 代码可以这样定义：int right = 1, left = 1;

（2）数组前一个数据我们可以通过当前下标-1去访问，不必大费周章再定义变量

（3）这两个题共同思想就是通过两个指针走不同的路来去遍历数组，最终的遍历次数均为一次，时间复杂度为O(N)，较好！当然如果没有空间的要求，可以创建一个新的数组，通过一个指针去遍历也是可以的，根据具体情况而定。

????如果再也不能见到你，祝你早安，午安，晚安???? 

????新的一月万事胜意，各位记得快乐???? 

相关文章