algorithm - 数组中交替的正数和负数

Question

给定一个由相等数量的正数和负数组成的数组（0 被认为是正数）。重新排列元素，使正数和负数交替放置，这样它应该就位并且元素的顺序不应该改变。有比 O(n2) 更好的解决方案吗？

Answer 1

对于数组，我不知道是否有可能比 O(n^2) 更好的解决方案，因为对数组的任何删除和插入都具有 O(n) 时间复杂度。

请注意，这里我们不是像快速排序算法那样交换值，而是删除并插入到数组中的新位置。

如果您将序列维护为链表，则 O(n) 时间解决方案是可能的。

保留2个指针。一个用于扫描列表，另一个用于跟踪交换索引。

只需扫描列表以查找交替的 + 和 - 数字。如果遇到 2 个连续的 +ve 数字，则在扫描的最后一个节点处停止跟踪指针。使用扫描指针继续扫描列表，直到遇到负数。

现在从其原始位置删除负索引节点，并将负索引节点插入到跟踪指针位置之前。将跟踪指针增加 1 步。这些操作可以在链表中在 O(1) 时间内完成。

同样对于负值。在任何时候，您只能拥有额外的正数或负数。

只需跟踪插入位置。

Answer 2

例如，如果输入数组是[-1, 2, -3, 4, 5, 6, -7, 8, 9]，那么

output should be [9, -7, 8, -3, 5, -1, 2, 4, 6]

解决方法是先用 QuickSort 的分区过程将正数和负数分开。在分区过程中，将 0 视为枢轴元素的值，以便将所有负数放在正数之前。将负数和正数分开后，我们从第一个负数和第一个正数开始，并将每个交替的负数与下一个正数交换。

// A C++ program to put positive numbers at even indexes (0, 2, 4,..) 
// and negative numbers at odd indexes (1, 3, 5, ..)
#include <stdio.h>

// prototype for swap
void swap(int *a, int *b);

// The main function that rearranges elements of given array.  It puts 
// positive elements at even indexes (0, 2, ..) and negative numbers at 
// odd indexes (1, 3, ..).
void rearrange(int arr[], int n)
{
    // The following few lines are similar to partition process
    // of QuickSort.  The idea is to consider 0 as pivot and
    // divide the array around it.
    int i = -1;
    for (int j = 0; j < n; j++)
    {
        if (arr[j] < 0)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    // Now all positive numbers are at end and negative numbers at
    // the beginning of array. Initialize indexes for starting point
    // of positive and negative numbers to be swapped
    int pos = i+1, neg = 0;

    // Increment the negative index by 2 and positive index by 1, i.e.,
    // swap every alternate negative number with next positive number
    while (pos < n && neg < pos && arr[neg] < 0)
    {
        swap(&arr[neg], &arr[pos]);
        pos++;
        neg += 2;
    }
}

// A utility function to swap two elements
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// A utility function to print an array
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%4d ", arr[i]);
}

// Driver program to test above functions
int main()
{
    int arr[] = {-1, 2, -3, 4, 5, 6, -7, 8, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    rearrange(arr, n);
    printArray(arr, n);
    return 0;
}
Output:

    4   -3    5   -1    6   -7    2    8    9

时间复杂度：O(n)，其中 n 是给定数组中的元素数。

辅助空间：O(1)