初识双指针

发布时间:2024年01月22日

双指针的使用

1. 移除元素

题目链接

1.1暴力解法
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size=nums.size();
        for(int i=0;i<size;i++){
            if(nums[i]==val){
                for(int j=i+1;j<size;j++){
                    nums[j-1]=nums[j];
                }
                i--;//这里容易出错,移除元素后所有元素向前赋值,所以当前位置需要重新判断
                size--;  
            }
        }
        return size;
    }
};
1.2双指针法
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow=0;//定义一个慢指针
        for(int fast=0;fast<nums.size();fast++){//快指针
            if(nums[fast]!=val){
                nums[slow++]=nums[fast];
            }
        }
        return slow;
    }
};

本题最常见的思路是两层循环,时间复杂度O( n 2 n^2 n2)。有没有办法可以让时间复杂度减小,可以采用双指针的方法,这里慢指针是指向去除元素后其余元素的存放下标,快指针是用来遍历数组,时间复杂度为O(n)。
实验测试结果:

暴力解法:
在这里插入图片描述
双指针:
在这里插入图片描述

文章来源:https://blog.csdn.net/qq_53280985/article/details/135715484
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。