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

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 (1) (помимо самих элементов, которые предполагается свободно изменяемыми) и время O (NlgN), разделите проблему на задачу размещения массивов, которые, как известно, имеют вид pnPNгде p и P представляют собой ноль или более положительных чисел, а n и N представляют 0 или более отрицательных чисел, в массивы вида pPnN.Любой двухэлементный массив будет автоматически иметь такую ​​форму.Учитывая два массива этой формы, найдите первое отрицательное число, следующее положительное число и последнее положительное число, и "вращайте" средние две секции массива (легко сделать в постоянном пространстве, и время, пропорциональное размеру массивабыть "закрученным").Результатом будет массив вида pPnN.Два последовательных таких массива образуют больший массив в форме pnPN.

Чтобы делать вещи в постоянном пространстве, начните с объединения всех элементов и перевода их в форму PN.Затем выполните все квартеты элементов, затем все октеты и т. Д. До общего размера массива.

Answer 2

Просто идея. Давайте рассмотрим более простую проблему:

Учитывая массив, где первая часть (Np элементы) содержит только положительные числа, а последняя часть (Nn элементы): только отрицательныеиз них.Как поменять местами эти части, сохраняя относительный порядок?

Самое простое решение - использовать инверсию:

inverse(array, Np + Nn); // whole array
inverse(array, Nn);      // first part
inverse(array+Nn, Np);   // second part

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

Answer 3

Вот реализация JavaScript решения qiwangcs :

function specialSort(A){
    let min = Number.MAX_SAFE_INTEGER, max = -Number.MAX_SAFE_INTEGER;
    for(let 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(let i=0; i<A.length; i++)
        A[i]-= min;
    const newMax = max-min+1;        
    //Save original negative values into new positions
    let currNegativeIndex = 0;
    for(let i=0; i<A.length; i++)
        if(A[i]%newMax < (-min))
            A[currNegativeIndex++] += (A[i]%newMax)*newMax;
    //Save original positive values into new positions
    let currPositiveIndex = currNegativeIndex;
    for(let i=0; i<A.length; i++)
        if(A[i]%newMax > (-min))
            A[currPositiveIndex++] += (A[i]%newMax)*newMax;
    //Recover to original value 
    for(let i=0; i<A.length; i++){
        A[i] = Math.floor(A[i]/newMax) + min; 
    }
}
// Demo
const A = [-3,-7,2,8,-5,-2,4];
specialSort(A);
console.log(A);

Answer 4

Я очень сомневаюсь, что время O (n) и O (1) возможно с массивом . Некоторые предлагают связанный список, но вам понадобится пользовательский связанный список, где у вас есть прямой доступ к узлам, чтобы сделать это, т.е. встроенные в язык связанные списки не будут работать.

Вот моя идея, используя custom вдвойне связанный список , который удовлетворяет ограниченным сложностям, используя в качестве примера [1, 7, -5, 9, -12, 15]:

Прокрутите список , если видите негатив, обрежьте его и добавьте к концу негативов спереди. Каждая операция равна O (1), поэтому общее время равно O (n). Операции со связанным списком выполняются на месте, поэтому O (1) пробел.

Подробно:

last_negative_node = null;

at -5: 

cut off -5 by setting 7.next = 9, 

then add -5 to front by -5.next = 1, 

then update last_negative_node = 5 // O(1), the linked list is now [-5, 1, 7, 9, -12, 15]


at -12: 

cut off -12 by setting 9.next = 15, 

then add -12 to front by -12.next = last_negative_node.next, 

then update last_negative_node.next = -12,

then update last_negative_node = -12 //O(1), the linked list is now [-5, -12, 1, 7, 9, 15]

no more negatives so done.

Answer 5

Чрезвычайно простое решение приведено ниже, но не в O (n). Я немного изменил алгоритм сортировки вставок. Вместо проверки, является ли число большим или меньшим, оно проверяет, больше или меньше оно нуля.

 int main() {

    int arr[] = {1,-2,3,4,-5,1,-9,2};

        int j,temp,size;

        size = 8;
        for (int i = 0; i <size ; i++){
            j = i;  
            //Positive left, negative right
            //To get opposite, change it to: (arr[j] < 0) && (arr[j-1] > 0)
            while ((j > 0) && (arr[j] >0) && (arr[j-1] < 0)){
                  temp = arr[j];
                  arr[j] = arr[j-1];
                  arr[j-1] = temp;
                  j--;
            }
        }

        //Printing
        for(int i=0;i<size;i++){
            cout<<arr[i]<<" ";      
        }
        return 0;
 }

Answer 6

Это не Сложность O (1) , а более простой подход.Оставить комментарий

void divide (int *arr, int len) {
    int positive_entry_seen = 0;                                                                                             
    for (int j = 0; j < len ; j++) { 
        if (arr[j] >= 0 ) { 
            positive_entry_seen = 1;
        } else if ((arr[j] < 0 ) && positive_entry_seen) {
            int t = arr[j];
            int c = j;
            while ((c >= 1) && (arr[c-1] >= 0)) {
                arr[c] = arr[c-1];
                c--;
            }   
            arr[c] = t;
        }   
    }   
}

Answer 7

Посмотрите на Heapsort в таблице алгоритмов сортировки в Википедии: http://en.wikipedia.org/wiki/Sorting_algorithm

Answer 8

Я думаю, что это сработает: вот простой способ - это постоянное пространство (но квадратичное время).Скажем, массив имеет длину N. Пройдите по массиву от i = 0 до i = N-2, проверяя элементы i и i + 1.Если элемент i положительный, а элемент i + 1 отрицательный, меняйте их местами.Затем повторите этот процесс.

Каждый проход по массиву заставит негативы смещаться влево (и позитивы смещаются вправо), что-то вроде пузырьковой сортировки, пока (после достаточного количества проходов) они не станутвсе на своем месте.

Кроме того, я думаю, что это будет работать: это также постоянное пространство (но квадратичное время).Скажи P - это число позитивов.Сканируйте слева направо, когда вы обнаружите положительный х, остановите сканирование и «удалите его», сдвинув все элементы после него на один.Затем поместите х в конце массива.Повторите процедуру сканирования P раз для перемещения каждого положительного.

Answer 9

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

int main()
{
    int array[TAM], num, i=0, j=0;

    printf("Ingrese arreglo: ");

    for(i=0; i < TAM -1 && num != 0; i++)
    {
        scanf("%d", &num);
        array[i]=num;
    }

    for(i=0; array[i] != 0 ; i++)
    {
        j++;
    }

    Alternar(array, j);

    //MOSTRAR
    for(i=0; i < j; i++)
    {
        printf("%d ", array[i]);
    }


    return 0;
}

void Alternar(int array[], int j)
{
    int i=0, aux, pasadas=1;

    for(pasadas=1; pasadas < j; pasadas++)
    {
        for(i=0; i < j - pasadas ; i++)
        {
            if(array[i] > 0 && array[i+1] < 0)
            {
                aux = array[i];
                array[i] = array[i+1];
                array[i+1] = aux;
            }
        }
    }

}

Answer 10

Вот мое решение в Python , использующее рекурсию (у меня было подобное назначение, где массив должен быть отсортирован относительно числа K. Если вы поставите K = 0, вы получите решение, без сохранения порядка появления ):

def kPart(s, k):
    if len(s) == 1:
        return s
    else:
        if s[0] > k:
            return kPart(s[1:], k) + [s[0]]
        else:
            return [s[0]] + kPart(s[1:], k)