leetcode 27 移除元素

2023-02-17 56

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： leetcode 27 移除元素

移除元素

第一次做的版本

理解有错误，不能使用额外的空间。

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        vector<int> temp;
        int i=0, j=0;
        for ( i = 0; i < nums.size(); i++)
        {
            if (nums[i] != val) 
            {
                temp.push_back(nums[i]);
                j++;
            }
        }
        nums = temp;
        return temp.size();
    }
};
int main()
{
    vector<int> my_nums = { 0,1,2,2,3,0,4,2 };
    int my_val= 2;
    Solution a;
    cout << a.removeElement(my_nums, my_val) << ", nums = [";
    for (int i=0; i < my_nums.size(); i++)
    {
        cout << my_nums[i] << ' ';
    }
    cout <<'}'<< endl;
  return 0;
}

暴力解法

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i=0, j=0;
        int size = nums.size();
        for ( i = 0; i <size; i++)
        {
            if (nums[i] == val) 
            {
                for (j = i; j < size-1; j++)
                {
                    nums[j] = nums[j + 1];
                }
                size--;
                i--;
            }
        }
        return size;
    }
};
int main()
{
    vector<int> my_nums = { 0,1,2,2,3,0,4,2 };
    int my_val= 2;
    Solution a;
    cout << a.removeElement(my_nums, my_val) << ", nums = [";
    for (int i=0; i < a.removeElement(my_nums,my_val); i++)
    {
        cout << my_nums[i] << ' ';
    }
    cout <<']'<< endl;
  return 0;
}

双指针法

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int fastIndex = 0, slowIndex = 0;
        for (fastIndex = 0; fastIndex < nums.size(); fastIndex++)
        {
            if (nums[fastIndex] != val)
            {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
};
int main()
{
    vector<int> my_nums = { 0,1,2,2,3,0,4,2 };
    int my_val= 2;
    Solution a;
    cout << a.removeElement(my_nums, my_val) << ", nums = [";
    for (int i=0; i < a.removeElement(my_nums,my_val); i++)
    {
        cout << my_nums[i] << ' ';
    }
    cout <<']'<< endl;
  return 0;
}

二刷

库函数删除

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        for(int i=0 ; i<nums.size() ;)
        {
            if(nums[i]==val)
            {
                nums.erase(nums.begin()+i);
                continue;
            }
            i++;
        }
        return nums.size();
    }
};

快慢指针

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int result =0;
        for(int i=0 ; i<nums.size() ;i++)
        {
            if(nums[i] != val)
            {
                nums[result] = nums[i];
                result++;
            }
        }
        return result;
    }
};