可以使用std :: sort()将零移动到数组的末尾？

Question

我正在研究这个问题:

给定一个数组nums,写一个函数将所有0移动到它的末尾,同时保持非零元素的相对顺序.

我知道如何通过就地交换来回答这个问题,但我也想知道是否有可能解决它std::sort.

根据cplusplus.com:

sort函数的比较器函数是一个二进制函数,它接受范围中的两个元素作为参数,并返回一个可转换为bool的值.返回的值表示作为第一个参数传递的元素是否被认为是在它定义的特定严格弱顺序中的第二个参数之前.

该函数不得修改其任何参数.

这可以是函数指针或函数对象.

//comments below are based on my understanding
static bool comp(int a, int b){
    //lambda function evaluates to true - no swap, 
    //evaluates to false -swap
    if(a==0) return false;
    if(b==0) return true;
    //if neither a nor b is 0 them do not swap
    return true;
}

void moveZeroes(vector<int>& nums) {
    sort(nums.begin(),nums.end(),comp);
}

给定的测试用例是 [0,1,0,3,12]

我的输出是 [12,3,1,0,0]

Answer 1

你几乎把它弄好了.在比较器功能中,您必须返回false不交换它们.此外,更改std::sort为std::stable_sort以保持原始顺序的值.

static bool comp(int a, int b)
{
    //lambda function evaluates to true - no swap, 
    //evaluates to false -swap
    if(a==0) return false;
    if(b==0) return true;
    //if neither a nor b is 0 them do not swap
    return false;
}

void moveZeros(std::vector<int>& nums)
{
    std::stable_sort(nums.begin(),nums.end(),comp);
}

现场演示