刷题打卡第二天（数组：快慢指针法）
source link: https://blog.51cto.com/u_15314328/5092527
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
（1）了解什么是暴力算法和快慢指针法
（2）在数组相关试题中，学会通过这两种方法来解决实际问题
（3）充分了解快慢指针法的应用场景
暴力算法：就是通过多层遍历的方式来解决一种问题，通过这类方法来解决问题，其时间复杂度会很高。
快慢指针法：就是通过使用两个变量变化（数组下标）来实现数组间的一些基本操作，来达到解决问题的目的。
例题：移除元素leetcode(数组：27)
问题分析：
方法一：暴力算法
对于这类问题，简单除暴的方法就是遍历数组，每一个值都和val进行比较判断，如果相等，就让该元素后的所有元素前移一位，然后总元素个数减少1；如果不相等，则只需一直往后遍历就行
过程图像理解如下：
方法一代码如下：
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]不相等时才会加加
代码实现过程如下：
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)
删除数组中的重复项
方法一：暴力算法
图像过程分析如下：
主要代码如下：
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;
}
};
方法二：快慢指针法：
图像过程分析如下：
主要代码如下：
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数
代码如下
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)
有序数组的平方
问题分析：
首先通过一层循环来讲数组的值变为其平方，然后使用快慢指针（两个变量）分别指向数组头和数组尾，然后通过比较其这两个值的大小，根据大小关系改变变量的值，将这两个数中的最大值来填充新的数组（从后往前），循环此过程，最终结果就是所求
错误思路：
初步分析也是通过分析这两个数的大小关系，只不过，如果左边的数小于右边的数时，不进行交换，反之，交换这两个数的值，无论是何种情况，后变量的值均会减少。但是这样的结果是不正确的，因为已经交换过的值和待交换的值的大小关系并不明确，无法保证能其结果是升序的。
图像演示如下：
public:
vector<int> sortedSquares(vector<int>& nums) {
int total=nums.size()-1;
vector<int>S(nums.size());
int begin=0,end=nums.size()-1;
for(int i=0;i<nums.size();i++)//将数组元素变为其二倍
nums[i]*=nums[i];
for(;begin<=end;)
{
if(nums[begin]>=nums[end]){
S[total--]=nums[begin++];
}
else
{
S[total--]=nums[end--];
}
}
return S;
}
};
总结：
从上述题中可以看出，使用暴力法来解决数组问题其时间复杂度会增加，并不是最好的解决方案，更好的解决方案是通过快慢指针法来解决，可以极大地降低时间复杂度，具体使用一定要结合具体的使用场景，如果涉及删除元素或需要变换元素组排列顺序时我们可以考虑使用快慢指针法来解决问题
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK