题目来源

• leetcode：27. 移除元素

题目描述

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {

    }
};

题目解析

快排

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

        return pos + 1;
    }
};

双指针

根据题意，我们可以将数组分成「前后」两段：

• 前半段是有效部分，存储的是不等于 val 的元素。
• 后半段是无效部分，存储的是等于 val 的元素。

最终答案返回有效部分的结尾下标。

int removeElement(vector<int>& nums, int val) {
    int n = nums.size();
    int left = 0;
    for (int right = 0; right < n; ++right) {
        if(nums[right] != val){
            nums[left] = val;
            left++;
        }
    }

    return left;
}

int removeElement(vector<int>& nums, int val) {
    if(nums.size() == 0){
        return 0;
    }

    int low = 0;       // 将所有不等于 val的 元素放到low的左边
    int high = nums.size() - 1;  //将所有val放到high的右边
    while (low < high){
        // 找到第一个 == val的数
        while (low < high && nums[low] != val){
            low++;
        }

        // 找到第一个 != val的数
        while(low < high && nums[high] == val){
            high--;
        }

        if(low < high){
            std::swap(nums[low], nums[high]);
        }
    }

    // 返回数组的长度
    if(nums[low] == val){
        return low;
    }

    // 数组中没有这个val
    return nums.size();
}

类似题目

最后

以上就是高贵大碗为你收集整理的leetcode：27. 移除元素题目来源题目描述题目解析类似题目的全部内容，希望文章能够帮你解决leetcode：27. 移除元素题目来源题目描述题目解析类似题目所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。