阅读量:0
注意：官方说法，快慢指针就是双指针。我在文章用两种不同的叫法，主要是根据字面意思更好的区分两个指针初始的指向，以便更快确定算法怎么写。
一、移除元素
对于数组来说，移除元素只是进行元素的“覆盖”。
解法：快慢指针法（两个指针初始位置都指向数组开头）
练习一：数组移除元素
题目描述：
给你一个数组 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; } 练习二：删除有序数组中的重复项
题目描述：
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
题目分析
- 需要判断fast和slow索引对应的数组元素是否重复，这样就明确了if的判断条件。
- 需要注意防止数组越界
- 程序有很多思路和写法，随便一种都可以
自己写的代码
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; } 练习三：删除有序数组中的重复项
题目描述：
给定一个数组 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; } } 官方代码 （这种做法很巧妙，需要好好理解）
将慢指针指向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++; } } 二、数组排序
解法：双指针法（初始位置一个指针指向数组开头，一个指向结尾）
因为不同于上面的数组元素前后位置不变，此时要比较数组元素大小，并排序。
练习：有序数组的平方
题目描述：
给你一个按 非递减顺序 排序的整数数组 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]
题目分析
- 需要排序，因此双指针分别指向数组头、数组尾。
- 此时，循环终止条件是 first <= last ;
- 要创建新数组，使用malloc分配空间。
- 新数组存元素可从头存，也可从尾寸；我这里从尾部存，所以每次存完，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; } 三、总结
- 简单删除元素 / 指定某元素位置，其余元素位置相对不变：
双指针指向数组头。快指针扫描数组并判断，慢指针收集变化后的数组元素。
不创建新数组，只覆盖原数组。 - 对数组元素排序：
一个指针指开头，一个指针指结尾。判断两指针指向值大小，循环结束条件first <= last；for循环，while循环均可，本人更习惯while循环。
使用malloc为新数组分配空间，注意，创建了新数组。
