LeetCode Problem 27 - Remove Element
Problem
Given an integer array nums
and an integer val
, remove all occurrences of val
in nums
in-place. The order of the elements may be changed. Then return the number of elements in nums
which are not equal to val
.
Consider the number of elements in nums
which are not equal to val
be k
, to get accepted, you need to do the following things:
- Change the array
nums
such that the firstk
elements ofnums
contain the elements which are not equal toval
. The remaining elements ofnums
are not important as well as the size ofnums
. - Return
k
.
The judge will test your solution with the following code:
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.
int k = removeElement(nums, val); // Calls your implementation
assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
Solution
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int k = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != val) {
nums[k++] = nums[i];
}
}
return k;
}
};
Explanation
This algorithm will always shift the numbers based on the counter k which holds the index for all elements without our value. This is initialized to 0. When we encounter our first non-value element, we place it at index k which is 0. By doing this, we ensure that any value within the first k elements do not include our value.