移除元素

问题描述：

给定一个数组nums和一个值val，要求原地移除所有数值等于val的元素。元素的顺序可能发生变化。然后返回在nums中与val不同的元素的数量。

问题建模：

假设nums中不等于val的元素数量为m，最后返回m，并把数组中所有与val相等的元素删除。

  • 返回数组中与val不相同的所有元素，不论排序

暴力求解法

介绍：使用两个for循环，时间复杂度高达 $ n^2 $ 的算法。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //使用for循环进行第一次暴力求解
        int dif = 0, i = 0;
        int len = nums.size();
        for(i = 0 ; i < len ; i++)
        {
            if(nums[i] == val)
            {//这里进行第二次暴力for循环求解
                for(int j = i + 1 ; j < len ; j ++)
                {
                    nums[j - 1] = nums[j];
                }
                i--;
                len--;
            }
            else
            {
                dif++;
            }
        }
        return dif;
    }
};

​ 稍微解释一下其中的要点：

  • 第一次循环做查找使用，第二次循环做覆盖元素使用
  • if中的i–和len–是做到重复覆盖的要点

此类解题方法的时间复杂度比较大，空间复杂度相对比较小。

快慢指针法

这是看了别人的解法学会的，所谓的快慢指针，也不是真的使用两个指针来执行，我觉得更合理点应该说是双变量快慢遍历，快变量遍历数组找到不与val相同的值做慢变量所找到的相同的替换。

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //快慢指针法
        int sptr = 0;
        for (int fptr = 0 ; fptr < nums.size() ; fptr++)
        {
            if (val != nums[fptr])
            {
                nums[sptr] = nums[fptr];   
                sptr++;
            }
        }

        return sptr;
    }
};

用慢指针去找到与val相同的值，并锁定，快指针继续往后移动，移动到第一个与val不相同的时候，赋值给慢指针，并继续同步移动，直到快指针遍历完一遍。

该方法的时间复杂度只有n，相较于暴力求解要快很多。