?
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
?
?
?
这题做下来感觉技巧性比较强，解出第一种解法以后我又尝试了另外两种解法，一个比一个简单。。。我一开始却折腾出了最晦涩的解法，可见一开始并没有对题目有深刻的理解。
?
首先说说第一种解法，思路就是：维护一个表示“下一个交换位置”的指针ex，初始为-1。遍历数组，当找到第一个elem的位置时，将ex指向他，
?
然后程序要做的就是在遍历过程中检查ex是否存在，存在的话就把当前数挪到ex处，同时把ex向前移动一位。
?
但是要注意一点是，当再次遇到elem时ex是不更新的。（也就是ex只是在elem第一次出现的时候为其赋值，然后就只用递增他就行了）
?
复制代码
int removeElement(int A[], int n, int elem) {
? ? int ex = -1;
? ? int len = n;
? ? for (int i = 0; i < n; i++) {
? ? ? ? if (A[i] == elem) {
? ? ? ? ? ? len--;
? ? ? ? ? ? if (ex < 0)
? ? ? ? ? ? ? ? ex = i;
? ? ? ? }
? ? ? ? else if (ex >= 0) {
? ? ? ? ? ? A[ex] = A[i];
? ? ? ? ? ? ex++;
? ? ? ? }
? ? }
? ? return len;
}
复制代码
这个解法虽然略显晦涩，但好处就是时间复杂度是O(n)，空间复杂度是O(1) ，算是一个比较理想的结果。
?
?
?
解法二：空间复杂度O(n)
使用额外的空间可以使思路变得简单，要做的就是从A里面逐一拷贝元素到aux里，其中跳过elem就行了。缺点就是提升了空间复杂度，还有到最后需要把aux
?
的值在重新赋值给A，这样时间复杂度也多了一倍到达了theta(2n)，空间复杂度为O(n)
?
复制代码
int removeElement2(int A[], int n, int elem) {
? ? int len = n;
? ? int aux[n];
? ? int k = 0;
? ? for (int i = 0; i < n; i++) {
? ? ? ? if (A[i] == elem) {
? ? ? ? ? ? len--;
? ? ? ? }
? ? ? ? else {
? ? ? ? ? ? aux[k++] = A[i];
? ? ? ? }
? ? }
? ??
? ? for (int i = 0; i < len; i++) {
? ? ? ? A[i] = aux[i];
? ? }
? ? return len;
}
复制代码
?
?
解法三：认真观察删除操作的性质会发现，删除一个元素不过就是把他后面的元素向前移动一位，那删除两个不就是移动两位，三个就是三位。。。以此类推。
?
所以我们只用在遍历数组的时候跟踪删除的个数n，然后同时将元素向后挪动n位就可以了，就这么简单。
?
复制代码
int removeElement3(int A[], int n, int elem) {
? ? int l = 0;
? ? for (int i = 0; i < n; i++) {
? ? ? ? if (A[i] == elem) {
? ? ? ? ? ? l++;
? ? ? ? }
? ? ? ? else if (l > 0){
? ? ? ? ? ? A[i-l] = A[i];
? ? ? ? }
? ? }
? ? return n-l;
}