One line c++ solution using std::stable_sort

  • 0
    void moveZeroes(vector<int>& nums) {
        std::stable_sort(nums.begin(), nums.end(), [](int a, int b){return a != 0 && b == 0;});

    update 2015/12/28:

    We need to "move all 0's to the end of it while maintaining the relative order of the non-zero elements", in other word, we can treat it as a sorting problem: all 0's are "larger" than other numbers. With this compare rule, all 0's will be moved to the end since they are "larger".

    The last parameter of "std::stable_sort" realizes this compare method which means if a != 0 and b == 0 then we say a < b. It is a Lambda function.

    However, we also have to keep the order of non-zero elements, so we pick a "stable sorting method" to make the sorting.

    You can refer to "Sorting algorithm" to see what the "stability" means.
    std::stable_sort this link shows the usage of std::stable_sort.

    Since the Algorithm complexity of all sorting algorithm should be at least nlog(n), This is not the best answer to this problem. But it is fast enough to past the test.

    Hope these can help. Sorry for my poor English.

  • 0

    Could you please explain more on how stable_sort fits for this question, especially on the third parameter part which I am not totally sure ? Thanks.

  • 0

    I have update the explanation of this post. Hope that helps.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.