arrays - 在任一侧重新排列阵列正负

Question

给定一组正整数和负整数，将一侧的所有正整数和一侧的负整数分组。这些数字应该与它们出现的顺序相同。

例子：

数组 = {1, -3, -5, 9, -8}

O/P = {-3, -5, -8, 1, 9}

我不认为使用额外空间对这个问题具有挑战性，因为您可以简单地循环并填充新数组。挑战是在不使用额外空间的情况下做到这一点。这个问题是我朋友问的。

（我正在考虑用 2 个指针解决它并交换正负等，但很快元素的相对顺序似乎就搞砸了）

有什么建议么？

Answer 1

这感觉像是作业，所以我会给你一个提示。

应用稳定排序。

稳定的排序算法保持具有相同键的记录的相对顺序。

作为你的平等测试，不要使用数字的实际值。相反，考虑任何正数等于任何其他正数，任何负数等于任何其他负数。

Answer 2

这可以是 O(n)。下面是python中的示例代码。在快速排序中使用 Pivot 可以解决问题。解决方案看起来像这样 -

def one_side_arrange(self, arr):
    i = -1
    for j in range(len(arr)):
        if (arr[j] < 0):
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    return arr

输入 Arr = [1,2,3,-1,2,-3,3,4,-3,-5] 输出 = [-1, -3, -3, -5, 2, 2, 3, 4 , 3, 1]