给出一个时间复杂度为O(n)的算法,该算法以数组S作为输入,将S分成三个集合:负数、零和正数。展示如何在原地实现,即不分配新内存。同时,您需要保持数字的相对顺序。 例如: {-1, 4, 0, -2, 1, 2} ==> {-1,-2,0,4,1,2}
我不确定是否存在这样的解决方案。我能想到的最好的解决方案有:
解决方案1:使用额外的整数数组,然后遍历整个数组以获取负数,然后是0,然后是正数。
解决方案2:不保留数字的相对顺序。然后循环遍历两次数组:
template <typename Type>
void Partion(Type *array, int begin, int end, Type v, int &l, int &r)
{
l = begin;
for (int i=begin; i!=end; ++i)
{
if (array[i] < v)
swap(array[i], array[l++]);
}
r = l;
for (int j=l; j!=end; ++j)
{
if (array[j] == v)
swap(array[j], array[r++]);
}
}
{-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 1, 2, 4}
。如果项目确实是排序的,那么-2应该在-1之前,而如果它们被分组为(-,0,+)
并且保持每个组内数字的相对位置不变,那么结果应该是{-1, -2, 0, 4, 1, 2}
,其中4出现在1和2之前。 - Anurag{1 -2 0 2 0 3 -1}
;第一次交换 =>{-2 -1 0 2 0 3 1}
;第二次交换 =>{-2 -1 0 0 2 3 1}
。如果你改用“冒泡交换”,那么时间复杂度又回到了N lg N。 - AShelly