锐客网

  1. 首页 > 睿知 > it技术 > >

刷题打卡第二天（数组（快慢指针法））

IT知识数组快慢指针

欠伸展肢体，吟咏心自愉。这篇文章主要讲述刷题打卡第二天（数组：快慢指针法）相关的知识，希望能为你提供帮助。

学习目标

?（1）了解什么是?暴力算法?和?快慢指针法??
?（2）在数组相关试题中，学会通过这两种方法来解决实际问题?
【刷题打卡第二天（数组（快慢指针法））】?（3）充分了解快慢指针法的应用场景?
?暴力算法：就是通过多层遍历的方式来解决一种问题，通过这类方法来解决问题，其时间复杂度会很高。?
?快慢指针法：就是通过使用两个变量变化（数组下标）来实现数组间的一些基本操作，来达到解决问题的目的。?
例题：?移除元素leetcode(数组：27)?

?问题分析：?
方法一：暴力算法
?对于这类问题，简单除暴的方法就是遍历数组，每一个值都和val进行比较判断，如果相等，就让该元素后的所有元素前移一位，然后总元素个数减少1；如果不相等，则只需一直往后遍历就行?
?过程图像理解如下：?

?方法一代码如下：?
class Solution
public:
int removeElement(vector< int> & nums, int val)
int total= nums.size(); //用来记录数组中元素总个数
for (int i=0; i< total; )//遍历数组
if(nums[i]==val)//判断

for(int j=i+1; j< total; j++)//其后数组元素整体前移
nums[j-1]=nums[j];
total--; //执行整体前移操作会覆盖数组中的val,元素个数减少1

else
i++; //如果条件不成立才会执行此操作，如果条件成立，因部分元素整体前移，所以i不需要变

return total;

;

?结果分析：?
?该算法的时间复杂度为O（n^2）,空间复杂度为O（1）?


方法二：左右指针法
?通过两个变量的变化来实现删除指定元素的方法，降低了时间复杂度?
?过程图像如下：?

?过程分析：?
?  如上图所示，slowIndex只有在val和nums[fastIndex]不相等时才会加加?
?代码实现过程如下：?
class Solution
public:
int removeElement(vector< int> & nums, int val)
int slowIndex=0;
for(int fastIndex=0; fastIndex< nums.size(); fastIndex++)
if(nums[fastIndex]!=val)

nums[begin]=nums[end];
slowIndex++;

return slowIndex;

;

相关试题：练习（一）：leetcode(数组：26)?删除数组中的重复项?

方法一：暴力算法?图像过程分析如下：?

?主要代码如下：?
class Solution
public:
int removeDuplicates(vector< int> & nums)
int sum=nums.size();
for(int i=1; i< sum; )
if(nums[i-1]==nums[i])

for(int j=i+1; j< sum; j++)
nums[j-1]=nums[j];
sum--;

else
++i;


return sum;


;



方法二：快慢指针法：
?图像过程分析如下：?

?主要代码如下：?
class Solution
public:
int removeDuplicates(vector< int> & nums)
if(nums.size()< 2) return nums.size(); //要注意判断数组为空和为1的情况
int i=0;
for(int j=1; j< nums.size(); j++)
if(nums[i]!=nums[j])
nums[++i]=nums[j]; 步步前移
return ++i; //在循环执行完后，i的结果标识的是数组下标，加上1后就是剩下数组的总元素个数

;

练习（二）：leetcode(数组：283)?移动零?
?题目描述：?

方法：快慢指针法?问题分析：?
?可以通过快慢指针的方法来解决这一个问题，当初次遇到0时，慢指针指向，然后如果快指针指向的是非零数，就将该数赋值给慢指针指向的位置，然后慢指针后移。快指针进行遍历，慢指针用来进行填充非0数?
?代码如下?
class Solution
public:
void moveZeroes(vector< int> & nums)
int total=nums.size();
int i,j; //通过快慢指针法来实现数组中非零数字的向前移动
for(i=0,j=0; j< total; j++)
if(nums[j]!=0)
nums[i++]=nums[j];


//当遍历循环后，需要将nums[i]及其后的元素全部变为0
while(i< j)
nums[i++]=0;



;

练习（三）：leetcode(数组：977)?有序数组的平方?

?问题分析：
?首先通过一层循环来讲数组的值变为其平方，然后使用快慢指针（两个变量）分别指向?数组头和数组尾，然后通过比较其这两个值的大小，根据大小关系改变变量的值，将这两个数中的最大值来填充新的数组（从后往前），循环此过程，最终结果就是所求
错误思路：?
?初步分析也是通过分析这两个数的大小关系，只不过，如果左边的数小于右边的数时，不进行交换，反之，交换这两个数的值，无论是何种情况，后变量的值均会减少。但是这样的结果是不正确的，因为已经交换过的值和待交换的值的大小关系并不明确，无法保证能其结果是升序的。?
?图像演示如下：?

方法：快慢指针法?实际代码如下：
class Solution
public:
vector< int> sortedSquares(vector< int> & nums)
int total=nums.

    推荐阅读


    上一篇：Linux中的计划任务—Crontab调度重复执行的任务

    下一篇：智慧化水务（降低污水处理过程中人力能耗成本）