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

avatar
作者
筋斗云
阅读量: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 。

题目分析
  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; } 

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

力扣链接

题目描述:
给定一个数组 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]

题目分析
  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. 对数组元素排序
    一个指针指开头,一个指针指结尾。判断两指针指向值大小,循环结束条件first <= last;for循环,while循环均可,本人更习惯while循环。
    使用malloc为新数组分配空间,注意,创建了新数组。

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!