[Leetcode 27]Remove Element

Desciption:

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. Return k after placing the final result in the first k slots of nums.

Example:

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 k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

C code solution

int removeElement(int* nums, int numsSize, int val){
int length = 0;
int duplicate = 0; // the accumulate left shift
for(int i=0; i<numsSize; i++){ //iterate numsSize-1 times
if(nums[i] == val){
duplicate++;
}else{
nums[i-duplicate] = nums[i];
length++;
}
}
return length;
}

Explanation:

用 變數duplicate 紀錄接下來的element需要往左幾格,若遇 nums[i] == val 的情況,將 length 加一。這樣的時間複雜度為O(n)。