Remove Elements from Array
Given an array and a value, remove all instances of that value in place and return the new length.
It doesn't matter what you leave beyond the new length.
Instead, if we count the number of known occurrence, we can move the next not-to-remove element directly to the right spot. By doing this, we only need to iterate through all elements once, which gives us an O(n) solution.
Given an array and a value, remove all instances of that value in place and return the new length.
It doesn't matter what you leave beyond the new length.
Instead, if we count the number of known occurrence, we can move the next not-to-remove element directly to the right spot. By doing this, we only need to iterate through all elements once, which gives us an O(n) solution.
public int removeElement(int[] A, int elem) {
int count = 0;
for (int i=0; i<A.length; ++i) {
if (A[i] == elem) { // find one, skip
++count;
} else if (count > 0) { // copy over
A[i-count] = A[i];
}
}
return A.length - count;
} int removeElement(int A[], int n, int elem) { // Start typing your C/C++ solution below // DO NOT write int main() function int i=0; int j=0; while (i<n){ if (A[i]!=elem){ A[j]=A[i]; j++; } i++; } return j; }
要求是in-place，那可以通过指针后移或者替换，替换的话顺序会变，这里正好让变。设置一头一尾的指针，从头遍历一旦遇到该value，就与尾部的数替换，最后头指针停留位置就是有效长度。
public int removeNumberInArray(int[] num, int target){
int i = 0, j = num.length-1;
while(i < j){
if(num[i]==target){
int temp = num[j];
num[j] = num[i];
num[i] = temp;
j--;
}else{
i++;
}
}
if(num.length==0){return 0;}
return num[i]==target?i:i+1;
}
Remove Duplicates from Sorted Array
Do not allocate extra space for another array, you must do this in place with constant memory.
Remove Duplicates from Sorted Array II
int i = 0, j = num.length-1;
while(i < j){
if(num[i]==target){
int temp = num[j];
num[j] = num[i];
num[i] = temp;
j--;
}else{
i++;
}
}
if(num.length==0){return 0;}
return num[i]==target?i:i+1;
}
Remove Duplicates from Sorted Array
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory. public int removeDuplicates(int[] A) {
int count = 0;
for (int i=1; i<A.length; ++i) {
if (A[i] == A[i-1]) { // skip duplicates
++count;
} else if (count > 0) { // copy over non-duplicates
A[i-count] = A[i];
}
}
return A.length - count;
} Remove Duplicates from Sorted Array II
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].
Related:
Coding Interview Questions: No. 32 - Remove Numbers in Array
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].
In the above problem, we only need to test the one right before the current one whichis not possible to have been overwritten. But now, we also need to test the one that is two nodes away which is possible to have been overwritten. That said, we should test the two nodes that are supposed to be ahead of the current node in the new array.
public int removeDuplicates(int[] A) {
int count = 0;
for (int i=2; i<A.length; ++i) {
if (A[i] == A[i-count-1] && A[i] == A[i-count-2]) { // skip duplicates
++count;
} else if (count > 0) { // copy over non-duplicates
A[i-count] = A[i];
}
}
return A.length - count;
}
Related:
Coding Interview Questions: No. 32 - Remove Numbers in Array
