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.

class Solution {
public:
    //这个版本的快排要记住
    //这个版本的Partition是 Hoare的版本
    int removeElement(int A[], int n, int elem) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i = 0,j = n-1;
        if (i > j){
            return 0;
        }
        int pivot = 0;
        //while(1)
        while(1){
            //while(<) 加上边界条件 MIT版本不需要
            while (i < n && A[i] != elem){
                i++;
            }
            //while(>)
            while(j >= 0 && A[j] == elem){
                j--;
            }
            //if (i<j)
            if (i < j){
                swap(A[i],A[j]);
            }else{
                //return j
                pivot = j;
                break;    
            }
        }
        return pivot + 1;
    }
};

using namespace std;
int main(int argc, char *argv[]) {
    int A[] = {2};
    int n = 1;
    Solution sol;
    int len = sol.removeElement(A,n,3);
    cout << len << endl;
    for(int i = 0; i < len; i++){
        cout << A[i] << " ";
    }
    cout << "\n";
    for(int i = len; i < n; i++){
        cout << A[i] << " ";
    }
}

原文链接: https://www.cnblogs.com/kwill/p/3189290.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍