移除元素

Question

  Given an array nums and a value val, remove all instances of that value in-place and return the new length.
  Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Clarification:
  Confused why the returned value is an integer but your answer is an array?
  Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

 // nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

**Example 1: **

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 2
It doesn’t matter what you leave beyond the returned length. For example if you return 2 with nums = [2,2,3,3] or nums = [2,3,0,0], your answer will be accepted.

**Example 2: **

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3]
Explanation: Your function should return length = 5 ,with the first five elements of nums containing 0, 1, 3, 0 and 4.Note that the order of those five elements can be arbitrary. It doesn’t matter what values are set beyond the returned length.

Constrains:

• 0 <= nums.length() <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

Answer

思路一

  堆栈法: 首先将nums中不等于val的值全部入栈，再将nums清空。再将没有val值的res的值重新的一一赋给nums，同时将res中的值一一弹出，最后直接返回nums数组的size即可。时间复杂度为O(n),空间复杂度为O(1).具体代码如下:

     class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        stack<int> res;
        
        for (int i = 0 ; i < n ;i++) {
            if (nums[i] != val) 
                res.push(nums[i]);
        }
        
        nums.clear();
        
        for (int i = 0 ; i < n ; i++) {
            if (!res.empty())
                nums.push_back(res.top()),res.pop();
        }
        return nums.size();
    }
};

思路二

  双指针法: 首先快慢指针置0，进入循环。如果nums数组对应的值不等于val,那么就把当前nums[fast]的值赋给nums[slow++]。如果相等那么fast就自增，最后结果返回slow的值。时间复杂度位O(n),空间复杂度O(1),具体代码如下：

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