给出一个 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++]);
}
}