秋高斋

双指针操作数组

发表于 更新于 分类于
本文字数： 1.1k 阅读时长 ≈ 2 分钟
使用双指针法操作数组，不需要额外的空间，原地修改数组。

双指针操作数组

双指针法，又称快慢指针法，是数组题中比较简单的一种。 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作，把复杂度为O(n^2)的暴力法优化为O(n)。 ## Example 之前做的题目，一两次就过了,没特别深的印象，等遇到难的题目再补充。

leetcode-27. 移除元素 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for(int fastIndex = 0; fastIndex < nums.size(); fastIndex++)
        {
            if(val != nums[fastIndex])
            {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;

    }
};

leetcode-26. 删除有序数组中的重复项 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slowIndex = 0;
        for(int fastindex = 1; fastindex < nums.size();fastindex++)
        {
            if(nums[fastindex] != nums[fastindex-1])
            {
                slowIndex++;
                nums[slowIndex] = nums[fastindex];
            }
        }
        return slowIndex + 1;
    }
};

leetcode-283. 移动零 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slowIndex = 0;
        for(int fastIndex = 0; fastIndex < nums.size(); fastIndex++)
        {
            if (nums[fastIndex] != 0)
            {
                nums[slowIndex++] = nums[fastIndex];
            } 
        }

        while(slowIndex < nums.size())
        {
                nums[slowIndex++] = 0;
        }

    }
};