LeetCode_Problem_27_Remove_Eleme

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.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example 1:
Givennums = [3,2,2,3], val = 3,
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.

题目要求空间复杂度为 O(1)，个人的思路是设置 i 和 idx 两个变量来保存下标，i 用来遍历数组，idx 用来索引当前的交换位置，遍历结束后 idx 的值也就是剩余元素的个数：

int removeElement(int* nums, int numsSize, int val) {
    int i = 0;
    int idx = 0;
    
    for (; i != numsSize; ++i) {
        if (nums[i] != val) {
            nums[idx++] = nums[i];
        }
    }
    
    return idx;
}

这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。

在网上还看到另一个差不多的解法，感觉有点别扭，还是把它记录下来：设置两个变量 idx 和 cnt，idx 用来遍历数组，cnt 保存已被删除的元素的个数。

for (idx = 0, cnt = 0; idx != numSize; ++idx) {
    if (nums[idx] == val) {
        ++cnt;
    } else {
        if (cnt > 0) {
            nums[idx - cnt] = nums[idx];
        }
    }
}
// length 当然是 idx - cnt 啦