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

Question

Недавно я столкнулся с вопросом об интервью Microsoft для инженера-программиста.

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

Например, учитывая [1, 7, -5, 9, -12, 15]
Ответ будет: [-5, -12, 1, 7, 9, 15]

Это должно быть сделано в O (n).

Мы могли бы легкосделать это в O (N), но я не могу думать, как мы можем поддерживать порядок элементов, как в исходном массиве.Если мы забудем о сложности O (n), может кто-нибудь сказать мне, как мы можем сохранить порядок элементов, не принимая во внимание сложность пространства и времени.

РЕДАКТИРОВАТЬ : В реальном вопросе мыдолжны также иметь O (1) сложность пространства.

Answer 1

Чтобы достичь этого результата в постоянном пространстве (но квадратичном времени), вы можете использовать подход с двумя очередями, помещая одну очередь в каждом конце массива (аналогично алгоритму голландского национального флага).Чтение элементов слева направо: добавление элемента в левую очередь означает оставление его в покое, добавление элемента в правую очередь означает смещение всех элементов, не входящих в очередь, на один и размещение добавленного элемента в конце.Затем, чтобы объединить очереди, просто измените порядок элементов во второй очереди.

Выполняет операцию O (n) (смещение элементов влево) до O (n) раз, что дает время работы O (n²).

Используя метод, подобный сортировке слиянием, вы можете добиться более низкой сложности O (n log n): разрезать массив на две половины, рекурсивно отсортировать их в виде [N P] [N P], а затем поменять местами первое P со вторым N за O (n) раз (это становится немного сложнее, когда у них разный размер, но он все еще линейный).

Я не имею ни малейшего представления о том, как сократить это до O (n) времени.

EDIT : на самом деле, ваше понимание связанного списка верно.Если данные представлены в виде двусвязного списка, вы можете реализовать стратегию с двумя очередями за время O (n), пространство O (1):

sort(list):
  negative = empty
  positive = empty
  while (list != empty)
     first = pop(list)
     if (first > 0) 
         append(positive,first)
     else
         append(negative,first)
  return concatenate(negative,positive)

С помощью реализации связанного списка, которая сохраняет указатели напервый и последний элементы, затем pop, append и concatenate являются операциями O (1), поэтому общая сложность составляет O (n).Что касается пробела, ни одна из операций не выделяет какую-либо память (append просто использует память, освобожденную pop), поэтому в целом это O (1).

Answer 2

Вот постоянная версия решения O (n) времени O (1), предполагается, что maxValue * (maxValue + 1) меньше, чем Integer.MAX_VALUE, где maxValue - результат значения maxmum минус значение minmum в массив. В качестве временного массива используется исходный массив для хранения результата.

public static void specialSort(int[] A){
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for(int i=0; i<A.length; i++){
        if(A[i] > max)
            max = A[i];
        if(A[i] < min)
            min = A[i];
    }
    //Change all values to Positive
    for(int i=0; i<A.length; i++)
        A[i]-= min;

    int newMax = max-min+1;

    //Save original negative values into new positions
    int currNegativeIndex = 0;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax < (-min))
            A[currNegativeIndex++] += (A[i]%newMax)*newMax;
    //Save original positive values into new positions
    int currPositiveIndex = currNegativeIndex;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax > (-min))
            A[currPositiveIndex++] += (A[i]%newMax)*newMax;
    //Recover to original value 
    for(int i=0; i<A.length; i++){
        A[i] = A[i]/newMax + min; 
    }
}

Answer 3

Я не уверен, что правильно понял вопрос, поскольку ответ кажется слишком простым:

• Пройдите по массиву и посчитайте отрицательные числа - O (n)
• Создать новый массив размером O (n)
• Пройдите по оригинальному массиву и поместите числа в новый массив. Используйте известное количество отрицательных чисел, чтобы сместить положительные - O (n)

Вот быстрый способ сделать это на Python. Он немного отличается от вышеупомянутого: сначала создается массив для негативов, а затем добавляется позитив. Так что это не так эффективно, но все равно O (n).

>>> a = [1,7,-5,9,-12,15]
>>> print [x for x in a if x < 0] + [y for y in a if y >= 0]
[-5, -12, 1, 7, 9, 15]

Редактировать: Хорошо, теперь с O (1) космической конкуренцией становится намного сложнее. Меня также интересует, как этого добиться в O (n) времени. Если это помогает, вот способ сохранить сложность пространства O (1), но требует сложности времени O (n ^ 2):

• Начните с крайнего левого отрицательного числа. Пройдите по массиву, пока не найдете следующее отрицательное число.
• В новом цикле замените отрицательное число на положительное число слева от него. Делайте это, пока не дойдете до других отрицательных чисел. Это гарантирует, что порядок номеров остается неизменным.
• Повторяйте и повторяйте, пока не достигнете конца массива при поиске нового отрицательного числа.

Answer 4

Это можно сделать в O (n) и пробел O (1).

Нам нужно 3 раза просканировать массив и тщательно изменить некоторые значения.

Предположение: максимальное значение в массиве с размером N должно быть меньше, чем (N+1) * Integer.MAX_VALUE.

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

• В первом сканировании найдите # отрицательных и положительных значений и максимальное значение.
• Во втором сканировании мы создаем отрицательный участок массива следующим образом:

Мы начинаем с начала массива и " swap " первым найденным положительным числом (например, по индексу i) с первым найденным отрицательным числом (например, j). Поскольку отрицательные числа рассматриваются в отношении их местоположения, обмен будет в порядке.

Проблема в положительных числах, потому что между i и j могут быть и другие положительные числа. Чтобы решить эту проблему, мы должны каким-то образом закодировать индекс положительного числа в этом значении перед заменой. Итак, мы можем понять, где это было в первой точке. Мы можем сделать это, a[i]=(i+1)*(max)+a[i].

• На третьем скане мы создаем положительный участок массива. к концу второго сканирования создается отрицательный массив, и положительные числа смещаются в правую сторону, но их расположение может быть неправильным. Таким образом, мы идем через это и исправляем их положение, так как в этой информации было закодировано их значение.

Вот код:

import java.util.Arrays;

public class LinearShifting {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = {-1,7,3,-5,4,-3,1,2};
        sort(a);
        System.out.println(Arrays.toString(a));  //output: [-1, -5, -3, 7, 3, 4, 1, 2]
    }
    public static void sort(int[] a){
        int pos = 0;
        int neg = 0;
        int i,j;
        int max = Integer.MIN_VALUE;
        for(i=0; i<a.length; i++){
            if(a[i]<0) neg++;
            else pos++;
            if(a[i]>max) max = a[i];
        }
        max++;
        if(neg==0 || pos == 0) return;//already sorted
        i=0;
        j=1;
        while(true){
            while(i<=neg && a[i]<0) i++;
            while(j<a.length && a[j]>=0) j++;
            if(i>neg || j>=a.length) break;
            a[i]+= max*(i+1);
            swap(a,i,j);
        }

        i = a.length-1;
        while(i>=neg){
            int div = a[i]/max;
            if(div == 0) i--;
            else{
                a[i]%=max;
                swap(a,i,neg+div-2);// minus 2 since a[i]+= max*(i+1);
            }
        }

    }
    private static void swap(int[] a, int i , int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}

Answer 5

Редактировать (29.05.2015): я упустил требование о поддержании порядка появления, поэтому приведенный ниже ответ не удовлетворяет всем требованиям вопроса.Однако я оставляю исходный ответ для общего интереса.

---

Это специальная версия очень важной подпрограммы быстрой сортировки, известной как «разделение».Определение: массив A, имеющий N числовых записей, делится на значение K по индексу p, если A [i] = K для p <= j <N, если только всезаписи меньше K (что означает p = N) или не меньше K (что означает p = 0).Для рассматриваемой проблемы мы разделим массив вокруг K = 0. </p>

Вы можете разбить несортированный массив на любое значение K за O (n) раз, получая доступ к каждой записи в массиве только один раз, используя O(1) дополнительная память.Неформально вы проходите массив с обоих концов, перемещая значения, которые находятся не на той стороне.Произведите своп, когда на каждой стороне массива будет найдено одно неуместное значение, затем продолжите шаг внутрь.Теперь код C ++:

// Assume array A[] has size N
int K = 0; // For particular example partitioning positive and negative numbers
int i = 0, j = N-1; // position markers, start at first and last entries
while(1) { // Break condition inside loop
    while(i < N && A[i] < K) i++; // Increase i until A[i] >= K
    while(j >= 0 && A[j] >= K) j--; // Decrease j until A[j] < K
    if(i < j) 
        swap(A[i],A[j]);
    else
        break;
}
// A[] is now partitioned, A[0]...A[j] < K, unless i==0 (meaning all entries >= K).

Обратите внимание, что если все элементы равны K (в данном случае, нулю), i никогда не увеличивается и j = 0 в конце.В постановке проблемы предполагается, что этого никогда не произойдет.Разделение очень быстрое и эффективное, и именно благодаря этой эффективности быстрая сортировка является самой популярной процедурой сортировки для больших массивов.Функция подкачки может быть std :: swap в C ++, или вы можете легко написать свою собственную:

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

Или просто для удовольствия, числа можно поменять местами без временной памяти, но помните о переполнении:

// This code swaps a and b with no extra space.  Watch out for overflow!
a -= b;
b += a;
a = b - a;

Существует много вариантов разделения для особых случаев, например, трехстороннее разделение для [elements K].Алгоритм быстрой сортировки вызывает разделение рекурсивно, и значение раздела K обычно является первой записью в текущем подмассиве или вычисляется из нескольких записей (например, медиана трех).См. Учебники: Алгоритмы Седжвика и Уэйна (4-е изд., Стр. 288) или Искусство компьютерного программирования, вып.3 Кнутом (2-е изд., Стр. 113).

Answer 6

Вот решение только с 2 итерациями:
Допустим, длина составляет п.
И я буду использовать C-подобный код, игнорируя синтаксические ошибки.

solution[n];
for (i= 0,j=0 ; i < n ; i++ ) {
     if (array[i] < 0) solution[j++] = array[i];
}
for (i = n-1,j=n-1 ; ; i > 0 ; i--) {
     if (array[i] >= 0) solution[j--] = array[i];
}

Идея состоит в том, чтобы пройти один раз и написать все негативы, с которыми мы сталкиваемся.
Затем пройдитесь по нему второй раз с конца и запишите положительные с конца по направлению к началу.

Answer 7

Это решение имеет O (n) сложность времени и O (1) сложность пространства.

Идея такова:

1. отслеживать индекс последнего увиденного отрицательного элемента (lastNegIndex).

2. перебрать массив, чтобы найти отрицательные элементы, которым предшествует положительный элемент.

3. Если такой элемент найден, поверните элементы вправо между lastNegIndex и текущим индексом на единицу.Затем обновите lastNegIndex (это будет следующий индекс).

Вот код:

public void rightRotate(int[] a, int n, int currentIndex, int lastNegIndex){
    int temp = a[currentIndex];
    for(int i = currentIndex; i > lastNegIndex+ 1; i--){
        a[i] = a[i-1];
    }
    a[lastNegIndex+1] = temp;
}

public void ReArrange(int[] a, int n){
    int lastNegIndex= -1;
    int index;

    if(a[0] < 0)
        lastNegIndex = 0;

    for(index = 1; index < n; index++){
         if (a[index] < 0 && a[index - 1] >= 0) {
             rightRotate(a, n, index, lastNegIndex);
             lastNegIndex = lastNegIndex + 1;
         }
    }
}

Answer 8

Вы можете использовать 2 очереди и объединить их. Таким образом, вы выполняете итерацию только один раз в первом массиве и один раз в каждой под-очереди.

negatives = []
positives = []

for elem in array:
  if elem >= 0:
    positives.push(elem)
  else
    negatives.push(elem)

result = array(negatives, positives)

Answer 9

Если структура в начале не должна быть массивом, это еще проще.

Если у вас есть исходные числа в связанном списке, это просто.

Вы можете перезапустить- упорядочить связанный список, просто каждый раз указывать отрицательный знак рядом со следующим отрицательным, а положительный - рядом со следующим положительным.

Снова C-подобный код, игнорируйте синтаксис.(может понадобиться проверка нуля здесь и там, но это идея)

Cell firstPositive;
Cell* lastPoisitive;
lastPoisitive = &firstPositive;
Cell firstNegative;
Cell* lastNegative;
lastNegative = &firstNegative;
Cell* iterator;
for(Iterator = list.first ; Iterator != null ; Iterator = Iterator->next) {
   if (Iterator->value > 0 ) lastPoisitive->next = Iterator;
   else lastPoisitive->next = Iterator;
}
list.first = firstNegative->next;
list.last.next = firstPositive->next;

Answer 10

O (n) решение Java

    private static void rearrange(int[] arr) {
    int pos=0,end_pos=-1;
    for (int i=0;i<=arr.length-1;i++){  
        end_pos=i;
        if (arr[i] <=0){
            int temp_ptr=end_pos-1;
            while(end_pos>pos){
                int temp = arr[end_pos];
                arr[end_pos]=arr[temp_ptr];
                arr[temp_ptr]=temp;
                end_pos--;
                temp_ptr--;
            }
            pos++;
        }

    }