Альтернативные положительные и отрицательные числа в массиве

Question

Для массива, состоящего из равного количества положительных и отрицательных чисел (0 считается положительным). Переупорядочивайте элементы таким образом, чтобы положительные и отрицательные числа помещались поочередно, таким образом, чтобы они были на месте, и порядок элементов не должен меняться. Есть ли решение лучше, чем O (n2)?

Answer 1

С массивом я не знаю, возможно ли решение лучше, чем O (n^2), потому что любое удаление и вставка в массив имеет сложность времени O (n).

Обратите внимание, что здесь мы не меняем значения, как в быстрых алгоритмах сортировки, но удаляем и вставляем в новое положение в массиве.

Решение времени O (n) возможно, если вы поддерживаете свою последовательность как связанный список.

Держите 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 (1)