977）网站首页 技术交流

数组--part 2--移除元素（力扣27/26/283/844/977）

Micoreal 2024-06-03 10:56:09

简介数组--part 2--移除元素（力扣27/26/283/844/977）

文章目录

基础代码讲解

从vector当中进行引入吧，我们首先默认读者知道数组是一个连续存储的空间，所以就有，当我们在准备删除其中一个数的时候，就需要面临着需要将其空间进行操作的过程，而erase函数实际上就是完成这样的一个过程，而且明显其时间复杂度是O(n)而非O(1)，因为需要把删除元素后的所有元素全部向前移一位，进行覆盖。

而对于实现这一过程，我们先看最简单的双循环法（暴力求解）：

//时间复杂度O(n2)
int removeElement(vector<int >& nums, int val)
{
	int size = nums.size();
	for (int i = 0; i < size; i++)
	{
		//当对应的值相等的时候进行每一位前移的操作
		if (nums.at(i) == val)
		{
			for (int j = j + 1; j < size; j++)
			{
				nums.at(j - 1) = nums.at(j);
			}
			//由于原本i的数进行删除了，而现在本位上的数据没有进行判断，所以需要再次进行判断，故需要i--
			i--;
			size--;
		}
	}
	return size;
}

这个暴力方法还是十分简单的，大家应该也常见过。

但是我们对于他的时间复杂度还不是很满意，我们可以使用双指针法进行相对应的优化。

定义快慢指针

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新新数组下标的位置

这边介绍两种常见的两种调换

时间复杂度都是O(n)

一：不改变原本顺序的调换：

int removeElement(vector<int >& nums, int val)
{
	int fast = 0, slow = 0;
	for ( fast = 0; fast < nums.size(); fast++)
	{
		if (nums.at(fast) != val)
		{
			//通过覆盖代替删除
			nums.at(slow++) = nums.at(fast);
		}
	}
	//数组大小也可以随之进行改变，这里就不改变了
	return slow;
}

二：改变相对顺序

int removeElement(vector<int >& nums, int val)
{
	//另一种就是一个指针在头，一个指针在尾部，进行的转化。
	int left = 0, right = nums.size() - 1;
	//值得关注的是此处需要加上等于，因为我们需要同时通过left和right进行判断其是否是不是val
	while (left <= right)
	{
		//从左边开始找，找第一个是val的数值
		//相同的关注一下是具有等号的
		while (left <= right && nums.at(left) != val)
			left++;
		//从右边开始找，找到第一个不是val的数值
		//相同的关注是有等号的
		while (left <= right && nums.at(right) == val)
			right--;
		//进行赋值操作
		//没有等于
		if (left < right)
			nums.at(left++) = nums.at(right--);
	}
	return left;
}

leetcode27 移除元素

链接

对于此题的话，实际上就只是需要理解一下之前的一些题目就可以了。

AC代码：

见上面的基本代码即可

leetcode26 删除排序数组中的重复项

链接

这一题实际上就是关于val的变化，将val改变成上一次填入数组的数据。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
    	//此处采用index储存上一次操作的数，而明显得知对于数组的第一个元素是一定存储下来的，故直接跳过。
        int index = nums[0];
        int fast = 0, slow = 1;
        for (fast = 1; fast < nums.size() ; fast++)
        {
            if (nums[fast] != index)
            {
                index = nums[fast];
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

leetcode283 移动零

链接

基础题型，还是靠理解开始的基础，唯一不同的就是需要对于val的处理进行稍微的调整，从原本的直接修改size的大小，到现在是将size之后的元素赋值为0，来进行操作的。

AC-code

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //由于需要保持两个的位置，所以，我们的双指针法采用同一节点开始。
        int fast = 0, slow = 0;
        for (fast = 0; fast < nums.size(); fast++)
        {
            if (nums[fast] != 0)
            {
                nums[slow++] = nums[fast];
            }
        }
        //剩下的全部赋值为0
        for (; slow < nums.size(); slow++)
        {
            nums[slow] = 0;
        }
    }
};

leetcode844 比较含退格的字符串

链接

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int s_fast = 0, s_slow = 0;
        int t_fast = 0, t_slow = 0;
        //先进行修改s字符串
        for ( s_fast = 0; s_fast < s.size(); s_fast++)
        {
            if (s[s_fast] == '#')
            {
                s_slow = s_slow > 0 ? s_slow - 1 : s_slow;
            }
            else
            {
                s[s_slow++] = s[s_fast];
            }
        }
        //同理修改t字符串
        for (t_fast = 0; t_fast < t.size(); t_fast++)
        {
            if (t[t_fast] == '#')
            {
                t_slow = t_slow > 0 ? t_slow - 1 : t_slow;
            }
            else
            {
                t[t_slow++] = t[t_fast];
            }
        }
        //进行判断是否相等,先判断size，然后便是字符串内部的元素
        if (s_slow != t_slow)
        {
            return false;
        }
        for (int i = 0; i < s_slow; i++)
        {
            if (s[i] != t[i])
            {
                return false;
            }
        }
        return true;
    }
};

当然写成一个函数是为了让读者可以比较充分的理解，也可以采用下述方式进行书写，希望读者可以尽量做到从上面的写法转化到下面的写法。（官方题解。）

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        return build(S) == build(T);
    }

    string build(string str) {
        string ret;
        for (char ch : str) {
            if (ch != '#') {
                ret.push_back(ch);
            } else if (!ret.empty()) {
                ret.pop_back();
            }
        }
        return ret;
    }
};