remove-element

Remove Element – LeetCode 27

Problem

Description

Given an array and a value, 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 in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example

Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Answer

Original

Code

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

思路

要求在一个数组中去除指定的元素，并返回修改后的长度。很明显与LeetCode 26相似，事实上也同样使用双指针的解法。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$3$ ms，排名$32.58\%$

Better

思路

虽然较好的做法是双指针，但依旧有可以优化的地方。原做法会导致额外的元素复制开销，通过将重复元素和末尾元素互换，可以只执行重复元素个交换操作。在重复元素少的情况下减少时间开销，利用的是题目中提到的数组顺序无关这一点。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$3$ ms，排名$32.58\%$

Code

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0;
        int n = nums.size();
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1];
                // reduce array size by one
                n--;
            } else {
                i++;
            }
        }
        return n;
    }
};