追寻数组的轨迹，解开算法的情愫

1. 移除元素

题目传送门

1.1 题目说明

题目描述： 给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，元素的顺序可能会发生改变。然后返回数组中与 val 不同元素的个数 k。

要求：

1. 修改数组 nums，使得数组的前 k 个元素包含所有与 val 不同的元素。
2. 数组剩余元素的顺序和大小无关紧要。

函数应返回：数组中 k 的值，即与 val 不同的元素的个数。

示例：

示例 1

• 输入：nums = [3, 2, 2, 3], val = 3
• 输出：2, nums = [2, 2, _, _]
• 解释：数组中的前两个元素为 2，移除元素 3。

示例 2

• 输入：nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2
• 输出：5, nums = [0, 1, 4, 0, 3, _, _, _]
• 解释：数组中的前五个元素为 0, 1, 4, 0, 3，移除了 2。

提示：

1. 数组的长度范围为：0 <= nums.length <= 100
2. 数组元素的值范围：0 <= nums[i] <= 50
3. 要移除的值 val 的范围：0 <= val <= 100

这道题的核心是双指针技巧，用一个指针遍历整个数组，另一个指针记录有效的（与 val 不同的）元素的位置。

1.2 题目分析

这个题让我们将数组中值等于val的进行删除的操作 那么我们就可以使用快慢指针进行操作了 但是这个并非是真正的指针，对于数组来说这个是下标 这个题其实很简单，我们定义快慢指针，快指针进行遍历数组的操作，如果快指针遍历到的数组的元素大小不等于val的话，那么我们就将当前位置赋值给慢指针的位置上面，然后慢指针进行++移动的操作，然后我们就间接的将这个val的值删除了 好的，让我举个具体的例子来说明这个解法。

如果把 i 变为慢指针，而 j 变为快指针，我们的解法和思路会稍有不同，但逻辑依然可以保持不变。具体来说，i 用来记录当前的有效位置，而 j 用来遍历数组。

修改后的思路：

• 快指针 j 遍历数组的每个元素。
• 慢指针 i 用来记录下一个不等于 val 的元素要存放的位置。

当我们发现 nums[j] 不等于 val 时，我们将 nums[j] 放到 nums[i] 的位置，然后将 i 向前移动。

具体实现步骤：

1. 初始化慢指针 i 为 0，表示下一个不等于 val 的元素要存放的位置。
2. 遍历数组 nums，使用快指针 j。
3. 如果 nums[j] != val，则将 nums[j] 复制到 nums[i]，并将慢指针 i 向前移动一位。
4. 最后，返回 i，此时它表示的是有效数组的长度。

举个例子：

假设输入：

• nums = [3, 2, 2, 3]
• val = 3

初始状态：

• nums = [3, 2, 2, 3]
• val = 3
• 慢指针 i = 0，快指针 j = 0

过程演示：

1. 第一轮：
   • j = 0，nums[0] = 3，等于 val，跳过。此时，i 不动。
   • 状态：nums = [3, 2, 2, 3]，i = 0，j = 1
2. 第二轮：
   • j = 1，nums[1] = 2，不等于 val，将 nums[1] 复制到 nums[i]，即 nums[0] = 2，然后 i++。
   • 状态：nums = [2, 2, 2, 3]，i = 1，j = 2
3. 第三轮：
   • j = 2，nums[2] = 2，不等于 val，将 nums[2] 复制到 nums[i]，即 nums[1] = 2，然后 i++。
   • 状态：nums = [2, 2, 2, 3]，i = 2，j = 3
4. 第四轮：
   • j = 3，nums[3] = 3，等于 val，跳过，i 不动。
   • 状态：nums = [2, 2, 2, 3]，i = 2，j = 4，遍历结束。

最终结果

• i = 2，表示新数组的长度为 2，即 nums 的前 2 个元素为 [2, 2]。
• 数组后面的部分内容无关紧要。

解释： 在整个过程中，快指针 j 负责遍历数组，找到不等于 val 的元素后将其复制到慢指针 i 所在的位置，并将慢指针 i 向前移动一位。最终，i 的值就是数组中不等于 val 的元素个数。

总结： 对于 nums = [3, 2, 2, 3]，移除 3 后的有效数组长度为 2，修改后的数组前两个元素为 [2, 2]。

1.3 代码部分

//使用双指针
//当快指针指向的值不等于要移除的 val 时，将该值赋给慢指针指向的位置，并移动慢指针
int removeElement(int* nums, int numsSize, int val)
{
    int i=0;//慢指针
    for(int j=0;j<numsSize;j++)//快指针遍历整个数组
    {
        if(nums[j]!=val)
        {
            nums[i]=nums[j];//将这个位置的值赋值给慢指针指向的位置
            i++;//慢指针往后移动
        }
    }
    return i;
}

1.4 代码分析

我们先定义变量i为0，用来当做慢指针，然后我们在for循环中定义j来当做快指针，我们在for循环中，我们进行判断，如果当前的j下标的值等于我们要删除的val的话，我们直接将这个跳过，但是如果我们遇到不等于val的值的话，我们就将当前的值赋值到i这个位置上面，然后我们的i进行加加的操作，出了循环之后，我们数组中的val已经被删除完了，因为题目让我们返回与val不同的元素，那么我们怎么操作呢？ 我们在for循环里面，我们进行了判断，如果不等于val的话，就让当前的值赋值到i的位置上面，并且我们的i也是会走一步的，那么我们i走了多少步，那么就存在多少个不等于val的元素，那么我们将i进行返回就行了

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

题目传送门

2.1 题目说明

给你一个 非严格递增排列 的数组 nums，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k，你需要做以下事情确保你的题解可以通过：

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

判题标准： 系统会用下面的代码来测试你的题解：

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1

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

示例 3

输入：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]。不需要考虑数组中超出新长度后面的元素。

提示：

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums 已按 非严格递增 排列

2.2 题目分析

因为给到我们的数组是有序的，那么这个重复的数字的话肯定是排列在一起的，重复元素是相邻的 我们可以初始化两个指针，i 指向数组的第一个元素，j 从第二个元素开始遍历。如果 nums[j] 和 nums[i] 不相等，说明 nums[j] 是一个新的不同的元素，将其放到 nums[i+1] 的位置上，然后i向前移动一位。那么我们就实现了将重复的第二个元素删除了 然后遍历完数组的话，我们的i+1就是我们新数组的长度了

2.3 代码部分

//只保留每个元素出现的第一个位置的那个元素
//因为这个数组是有序的，所以重复元素肯定是相邻的
//使用一个慢指针 i 来跟踪去重后的数组，并使用一个快指针 j 来遍历数组。
//只要当前元素 nums[j] 不等于 nums[i]（即发现了新的元素），就将 nums[j] 放到 i 的下一个位置，并更新 i 的位置。

/*
如果数组为空或者只有一个元素，直接返回数组的长度即可。
初始化两个指针，i 指向数组的第一个元素，j 从第二个元素开始遍历。
如果 nums[j] 和 nums[i] 不相等，说明 nums[j] 是一个新的不同的元素，将其放到 nums[i+1] 的位置上，然后 i 向前移动一位。
遍历完数组后，i + 1 就是新数组的长度。*/
int removeDuplicates(int* nums, int numsSize)
{
    if(numsSize==0)//数组为空，直接返回长度0
    {
        return 0;
    }


    int i =0;
    for(int j=1;j<numsSize;j++)
    {
        if(nums[j]!=nums[i])//发现新元素
        {
            i++;//换下一个元素进行寻找
            nums[i]=nums[j];//将新元素放到重组后的数组中
        }

    }
    //到这里的话就是已经完成了操作重复项了
    return i+1;//返回去重后的数组的长度
}

2.4 代码分析

我们先对特殊情况进行判断，若果当前的数组是空的话，那么我们直接返回0就行了 然后我呢定义一个指针i，初始化为0，然后再定义一个指针j，初始化为1，我们利用j进行遍历数组 如果当前j指向的数字的和我们的i指向的数字是不一样的话，不那么我们就让i往右走一步，然后我们将当前j指向的数字放到我们的i的位置 举个例子： 一个数组：1 1 2 一开始我们的i指向我们的第一个1，j指向我们的第二个1，然后我们进行循环里面的判断操作，因为当前的j下标的元素等于i的指向的元素，那么我们不进行操作，然后我们的j++，j指向我们的2，然后我们的2不等于1，所以我们直接先让i走到第二个i个位置，然后我们将j指向的2赋值到当前i的位置，然后我们的数组就变成这样子了 1 2 2 实际的数据只有两个了 那么我们怎么返回删除重复元素的数组的长度呢？ 因为我们的i是0开始的，然后只要遇到不同的元素，我们的i就进行加加的操作，那么我们的数组长度就是i+1，那么我们返回i+1就行了，这个就是我们有效数组的长度了