首页 > ACM题库 > LeetCode > LeetCode-Remove Element[数组]
2014
11-18

LeetCode-Remove Element[数组]

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

标签: Array Two Pointers
分析

代码1

// LeetCode, Remove Element
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        int index = 0;
        for (int i = 0; i < n; ++i) {
            if (A[i] != elem) {
                A[index++] = A[i];
            }
        }
        return index;
    }
};

代码2

// LeetCode, Remove Element
// 使用remove(),时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        return distance(A, remove(A, A+n, elem));
    }
};

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。