数据结构与算法--【数组2】力扣练习 || 双指针 / 移除元素 / 数组排序

注意：官方说法，快慢指针就是双指针。我在文章用两种不同的叫法，主要是根据字面意思更好的区分两个指针初始的指向，以便更快确定算法怎么写。

一、移除元素

对于数组来说，移除元素只是进行元素的“覆盖”。

解法：快慢指针法（两个指针初始位置都指向数组开头）

练习一：数组移除元素

力扣链接

题目描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

题目分析

题目要求我们移除（删掉）数组中的元素。但我们必须清楚一点：数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。对于数组，“删除”体现在实际算法中就是“覆盖”。 直接忽略要删除的值，重点关注剩下要组成的数组的元素，这句话在下面算法中体现在if判断语句。没有创建新数组，是对旧数组做一个“大扫除”。

代码

int removeElement(int* nums, int numsSize, int val) {
    int slow = 0;
    for(int fast = 0; fast < numsSize; fast++){
        if(nums[fast] != val){    //如果不是要删除的值，放进数组里
            nums[slow++] = nums[fast];  //nums[fast]先赋给nums[slow]，后slow++
        }
    }
    return slow;
}
1
2
3
4
5
6
7
8
9

练习二：删除有序数组中的重复项

力扣链接

题目描述：
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

题目分析

1. 需要判断fast和slow索引对应的数组元素是否重复，这样就明确了if的判断条件。
2. 需要注意防止数组越界
3. 程序有很多思路和写法，随便一种都可以

自己写的代码

int removeDuplicates(int* nums, int numsSize) {
    int slow = 0;
    for(int fast = 1; fast < numsSize; fast++){
        if(nums[slow] != nums[fast]){
            slow++;
            nums[slow] = nums[fast];
        }   
    }
    return slow+1;
}
1
2
3
4
5
6
7
8
9
10

练习三：删除有序数组中的重复项

力扣链接

题目描述：
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

自己写的代码

void moveZeroes(int* nums, int numsSize) {
    int slow = 0;
    for (int fast = 0; fast < numsSize; fast++) {
        if (nums[fast] != 0) {
            nums[slow++] = nums[fast];
        }
    }
    // 将数组剩余的部分设为0
    for (int i = slow; i < numsSize; i++) {
        nums[i] = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

官方代码 （这种做法很巧妙，需要好好理解）

将慢指针指向0，将快指针判断不为0的元素和慢指针交换位置；将指针传参，直接改变值。

void swap(int *a, int *b) {
    int t = *a;
    *a = *b, *b = t;
}

void moveZeroes(int *nums, int numsSize) {
    int left = 0, right = 0;
    while (right < numsSize) {
        if (nums[right]) {
            swap(nums + left, nums + right);
            left++;
        }
        right++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、数组排序

解法：双指针法（初始位置一个指针指向数组开头，一个指向结尾）

因为不同于上面的数组元素前后位置不变，此时要比较数组元素大小，并排序。

练习：有序数组的平方

力扣链接

题目描述：
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

题目分析

1. 需要排序，因此双指针分别指向数组头、数组尾。
2. 此时，循环终止条件是 first <= last ;
3. 要创建新数组，使用malloc分配空间。
4. 新数组存元素可从头存，也可从尾寸；我这里从尾部存，所以每次存完，k–；

自己写的代码

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* ret = (int*)malloc(sizeof(int) * numsSize);
    int i = 0, j = numsSize - 1;
    int k = numsSize - 1;
    while(i <= j){
        if(nums[i]*nums[i] > nums[j]*nums[j]){
            ret[k] = nums[i]*nums[i];
            i++;
        }else{
            ret[k] = nums[j]*nums[j];
            j--;
        }
        k--;  //每次循环结束k才会自减
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三、总结

1. 简单删除元素 / 指定某元素位置，其余元素位置相对不变：
   双指针指向数组头。快指针扫描数组并判断，慢指针收集变化后的数组元素。
   不创建新数组，只覆盖原数组。
2. 对数组元素排序：
   一个指针指开头，一个指针指结尾。判断两指针指向值大小，循环结束条件first <= last；for循环，while循环均可，本人更习惯while循环。
   使用malloc为新数组分配空间，注意，创建了新数组。