Remove Element


Hi, I have a problem with running solution.
I wrote the next solution: http://take.ms/vnqSp (it may not be optimal but it doesn't matter in this case). As you can see, the result is an array with 2 elements: {2, 2}.
But running code on your mashine show me the next output: http://take.ms/IQEhg ({3, 2}) I use neither global variables, nor C/C++. What could be the problem here?

@ivan70 The reason is you're assigning an array to nums inside the function, and the caller has no idea that nums had changed. This is similar to the following:
public void foo(int x) { x = 3; // change the copy of x to 3, which had no effect on the original x. } int x = 4; foo(x); System.Console.WriteLine(x); // still prints 4.
Therefore, the only way to change nums is to do something like
nums[0] = 4;
, which will change the values in nums array. This is howinplace
modification works.


@michahell I'm not sure what you mean by "wont work". I submitted your solution, and LeetCode accepted it as valid. It ranked among one of the slower solutions. Here are some concerns about your solution:

Python's builtin remove function might not be inplace. It might generate a new list which violates one of the problem's constraints. However, I'm betting it really is inplace. The builtin functions are coded to be fast and efficient.

The solution is slow. 'in' is O(n) and 'remove' is O(n), making your solution O(n^2). You should aim for an O(n) solution, though this wasn't explicitly specified as a constraint.


avoid the useless write.
public int removeElement(int[] nums, int val) { int l = 0, r = nums.length1; while(l < r) { while(l < nums.length && nums[l] != val) l++; while(r >= 0 && nums[r] == val) r; if(l < r) { nums[l] = nums[r]; nums[r] = val; l++; r; } else break; } if(l == r && nums[l] != val) l++; return l; }

My solution is similar to solution 2 but adding an step to ensure that nums[n1], the number swapped with the disposed one, must be a valid number.
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
if (nums.empty()) return 0;
int i = 0, j= nums.size();
while (i<nums.size()) {
if (nums[i] == val) {
while (j>i) {
j;
if (nums[j] != val) {
//switch nums[i] and nums[j]
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
break;
}
}
if (i >= j) break;
}
++i;
}
return i;
}
};

@kvelury
Read the question carefully.
You need to modify the array itself. Instead of just return the count.