Leetcode027

LeetCode027：移除元素         给你一个数组 nums 和一个值 val，你需要 "原地" 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 ```cpp 示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

注意: 你不需要考虑数组中超出新长度后面的元素。

#### 解法一：基于for范围的单标记方法 (执行用时 4ms, 内存消耗6.3MB)

&#160; &#160; &#160; &#160;<font color="black" size="4">首先定义一个标记new_idx，然后使用基于for范围的遍历数组，
如果数组中的元素n不等于val, 则将n赋值给下标new_idx对应的元素</font>

```cpp
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int new_idx = 0;
        for (auto n : nums) {
            if (n != val) {
                nums[new_idx] = n;
                new_idx++;
            }
        }
        return new_idx;
    }
};

解法二：基于for循环的单标记方法 (执行用时 4ms, 内存消耗6.2MB)

       首先定义一个标记new_idx，然后使用基于for循环的遍历数组，
如果数组中的元素nums[i]不等于val, 则将nums[i]赋值给nums[new_idx]。

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

解法三：基于for循环的方法 (执行用时 0ms, 内存消耗6.3MB)

       1.定位到第一次出现val的位置，赋值给i。
2.从j=i+1位置出发出一次遍历整个数组，当nums[j]!=val时将该位置数值移动到i位置，
并做i++；当nums[j]==val时则跳过该位置的数。
3.此时i是位于新数组的后面一位，所以i就是新数组的长度，返回即可。

class Solution3 {
public:
    int removeElement(vector<int>& nums, int val) {
        // if(nums.size() < 2)
        unsigned i;
        for (i = 0; i<nums.size(); i++)
            if (nums[i] == val) break; // 定位到第一个val的位置
        for (unsigned j = i + 1; j<nums.size(); j++)
        {
            if (nums[j] == val) continue;
            nums[i] = nums[j];
            i++;
        }
        return i;
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> nums;
    int Size;
    cout << "请输入数组nums的大小： " << endl;
    cin >> Size;
    cout << "请输入数组nums中的元素： " << endl;
    int Currval;
    for (int i = 0; i < Size; i++)
    {
        cin >> Currval;
        nums.push_back(Currval);
    }
    cout << "请输入目标值： " << endl;
    int val;
    cin >> val;
    Solution answer;
    cout << "剔除目标值后数组的大小为： " << answer.removeElement(nums, val) << endl;
    /*for (auto n : nums)
        cout << n << " ";*/

    system("pause");
    return 0;
}