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

Question

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

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

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

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

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

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

Answer 1

#include <iostream>

using namespace std;

void negativeFirst_advanced (int arr[ ], int size)

{

    int count1 =0, count2 =0;

    while(count2<size && count1<size)
{

        if(arr[count1]>0 && arr[count2]<0)
        {       
            int temp = arr[count1];
            arr[count1] = arr[count2];
            arr[count2] = temp;
        }

        if (arr[count1]<0)
            count1++;
        if (arr [count2]>0)
            count2++;

    }
}

int main()
{

        int arr[6] = {1,7,-5,9,-12,15};
        negativeFirst_advanced (arr, 6);
        cout<<"[";
        for (int i =0; i<6;i++)
            cout<<arr[i]<<" , ";
        cout<<"]";

        system("pause");
        return 0;
}

Answer 2

Используется процесс разбиения QuickSort.Временная сложность этого решения составляет O (n2), а вспомогательное пространство - O (1).Этот подход поддерживает порядок появления и не использовал никакой другой структуры данных.Это в Ruby

def sortSeg(intArr)
    intArr.each_with_index do |el, idx|
        # if current element is pos do nothing if negative,
        # shift positive elements of arr[0..i-1],
        # to one position to their right */
        if el < 0
            jdx = idx - 1;
            while (jdx >= 0 and intArr[jdx] > 0)
                intArr[jdx + 1] = intArr[jdx];
                jdx = jdx - 1;
            end
            # Insert negative element at its right position
            intArr[jdx + 1] = el;
        end
    end
end

Answer 3

Надеюсь, это поможет. У этого есть Сложность Времени O (n ^ 2)

#include <stdio.h>

int main() {
    int a[] = {-3, 2, -5, 9, -2, -8, 6, 8, -1, 6};

    int length = (sizeof(a) / sizeof(int));
    int i, j = 0;

    printf("Size of array: %d\n", sizeof(a));

    for (i = 0; i < length; i++) {
        if (i % 2 == 0 && a[i] < 0) {
            for (j = i + 1; j < length; j++) {
                if (a[j] > 0) {
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                    break;
                }
            }
        } else if (i % 2 == 1 && a[i] > 0) {
            for (j = i + 1; j < length; j++) {
                if (a[j] < 0) {
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                    break;
                }
            }
        }
    }

    for (i = 0; i < length; i++) {
        printf("Value at %d: %d\n", i, a[i]);
    }

    return 0;
}

РЕДАКТИРОВАТЬ 1 Это основывается на том факте, что числа больше нуля всегда имеют четный индекс, а числа меньше нуля всегда имеют нечетный индекс

РЕДАКТИРОВАТЬ 2 Код немного улучшен

Answer 4

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

    int[] n={2,-3,1,5,-10,-8};
    int k=0;
    for(int i=1;i<n.length;i++)
    {
        int temp=0;
        if(n[i]<0)
        {
            temp=n[k];
            n[k]=n[i];
            n[i]=temp;
            k++;
        }
    }

        for(int j=0;j<n.length;j++)
    {
        System.out.println(n[j]);
    }

Answer 5

Сначала посчитайте количество k отрицательных элементов. Затем вы знаете, что первые k числа массива (первая часть массива) должны быть отрицательными. Следующие элементы N - k должны быть положительными после сортировки массива.

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

Это требует O (1) хранения и занимает O (N) время.

Реализация на C ++:

#include <iostream>
#include <vector>

using namespace std;

void swap(vector<int>& L, int i, int j) {
    int tmp = L[i];
    L[i] = L[j];
    L[j] = tmp;
}

void signSort(vector<int>& L) {
    int cntNeg = 0, i = 0, j = 0;
    for (vector<int>::iterator it = L.begin(); it < L.end(); ++it) {
        if (*it < 0) ++cntNeg;
    }
    while (i < cntNeg && cntNeg + j < L.size()) {
        if (L[i] >= 0) {
            swap(L, i, cntNeg + j);
            ++j;
        } else {
            ++i;
        }
    }
}

int main(int argc, char **argv) {
    vector<int> L;
    L.push_back(-1);
    L.push_back(1);
    L.push_back(3);
    L.push_back(-2);
    L.push_back(2);
    signSort(L);
    for (vector<int>::iterator it = L.begin(); it != L.end(); ++it) {
        cout << *it << endl;
    }
    return 0;
}

Answer 6

Это можно просто сделать, выполнив шаги в O (n), без использования лишних пробелов

int count = 0;
//data is the array/vector in sort container having given input.
if(data[0] < 0)
    count++;
for(int i = 1; i < n; i++)
{
    if(data[i] < 0)
    {
        int j = i;
        while(j> count)
        {
            data[j-1] += data[j];
            data[j] = (data[j-1]-data[j]);
            data[j-1] -= data[j];
            j--;
        }
        count++;
    }
}

полную реализацию можно найти здесь https://gist.github.com/Shravan40/8659568

Answer 7

Простое и легкое решение, которое работает за O (n) сложность времени.

    int left = 0;
    int right = arr.length - 1;

    while (left < right) {

        while (arr[left] >= 0) {
            left++;
        }

        while (arr[right] < 0) {
            right--;
        }

        if (left < right) {
            ArrayUtility.swapInArray(arr, left, right);
    }

    ArrayUtility.printArray(arr);

Answer 8

Этот код Работа с O (n) сложностью и O (1) пробелом. Нет необходимости объявлять другой массив.

#include <stdio.h>

int* sort(int arr[], int size)
{
    int i;
    int countNeg = 0;
    int pos = 0;
    int neg = 0;

    for (i = 0; i < size; i++)
    {
        if (arr[i] < 0)
            pos++;
    }

    while ((pos < (size-1)) || (neg < size-(pos-1)))
    {
        if ((arr[pos] < 0) && (arr[neg] > 0))
        {
            arr[pos] = arr[pos] + arr[neg];
            arr[neg] = arr[pos] - arr[neg];
            arr[pos] = arr[pos] - arr[neg];
            pos++;
            neg++;
            continue;
        }
        if ((arr[pos] < 0) && (arr[neg] < 0))
        {
            neg++;
            continue;
        }
        if ((arr[pos] > 0) && (arr[neg] > 0))
        {
            pos++;
            continue;

        }
        if ((arr[pos] > 0) && (arr[neg] < 0))
        {
            pos++;
            neg++;
            continue;

        }
    }
    return arr;
}

void main()
{
    int arr[] = { 1, 7, -5, 9, -12, 15 };
    int size = sizeof(arr) / sizeof(arr[0]);
    sort(arr, size);
    int i;
    for (i = 0; i < size; i++)
    {
        printf("%d ,", arr[i]);
    }
    printf(" \n\n");
}

Answer 9

int [] input = {1, 7, -5, 9, -12, 15};
int [] output = new int [input.length];
int negativeIdx = 0;
int positiveIdx = input.length - 1;
for(int i = 0; i < input.length ; i++) {
    if(input[i] < 0) {
        output [negativeIdx++] = input[i];
    } else {
        output [positiveIdx--] = input[i];
    }
}
System.out.println

(Arrays.toString(output));

Выход:

[-5, -12, 15, 9, 7, 1]

Answer 10

здесь мой ответ - два отдельных положительных и отрицательных значения в одном массиве, это поможет вам

int[] singleArray= {300, -310, 320, 340, 350,
                -330, 420, 370, -360, 390,
                340, -430, 320, -463, 450}; 
public double[] getPositive_SingleArray() {
            double minValue = 0;
            double positiveValue=0;
            int count=0;
            for (int i = 0; i < singleArrayData.length; i++) {
                if ( singleArrayData[i]>0)
                    count++;
            }
            positiveSingleArrayData=new double[count];
            int k=0;
            for (int i = 0; i < singleArrayData.length; i++) {
                if ( singleArrayData[i]>0){
                positiveSingleArrayData[k] = singleArrayData[i];
                k++;
                }
             }
            System.out.println("single array of positve values "+Arrays.toString(positiveSingleArrayData));
            return positiveSingleArrayData;
        }