algorithm - 配列内の正と負の交互の数値

Question

同数の正と負の数で構成される配列が与えられます (0 は正と見なされます)。正の数と負の数が交互に配置されるように要素を再配置し、要素の順序が変わらないようにします。O(n2) よりも優れたソリューションはありますか?

Answer 1

たとえば、入力配列が[-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)