Сначала расположите нечетные числа, а затем четные. порядок нечетных четных не должен быть изменен - PullRequest
Новая
       6

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

0 голосов
/ 07 мая 2018

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

вход - {1, 4, 8, 3, 9, 12, 7} выход - {1, 3, 9, 7, 4, 8, 12}

Можем ли мы улучшить это из O (n2) в пространстве (без использования дополнительного пространства)? 

public  static void reOrder(int[] arr) {
     int evenIndex  = arr.length;
     for(int i=0; i < arr.length;i++) {
            if(arr[i] % 2 == 0 && evenIndex == arr.length) //even index
                evenIndex = i;

            else if( arr[i] % 2 != 0 ) {
                if(i > evenIndex ) {
                    shift (arr, evenIndex , i);
                    evenIndex ++;
                }
            }
     }
}

static void shift(int[] arr, int evenIndex, int endIndex) {
    int temp = arr[endIndex];
    for(int i = endIndex; i > evenIndex ;i --) {
        arr[i] = arr[i-1];
    }
    arr[evenIndex] = temp;
}

1 Ответ

0 голосов
/ 07 мая 2018

Вы не указали какой-либо языковой тег, поэтому я отвечу, используя python (только потому, что сейчас я использую его быстрее).

Если вы только заботитесь о сложности пространства, вы можете сделать что-то вроде этого: 

l = [1, 4, 8, 3, 9, 12, 7]
even_index = -1

for index in range(0, len(l)):
    if (l[index] % 2) == 0:
        if even_index == -1:
            even_index = index
    else:
        if (index > 0) and (even_index > -1):
            num = l[index]
            l.insert(even_index, num)
            del l[index + 1]
            even_index += 1
print(l)

Вы сохраняете указатель того, где находится первое четное число, и вставляете нечетное число, когда вы находите их, проходя через список. Затем вы удаляете нечетное число по «старому» индексу (который теперь увеличивается на 1).

Я думаю, вам нужна космическая сложность, но временная сложность может быть улучшена.

Например, в Python collections.deque, вероятно, лучше в этом случае, но сложность времени не была приоритетом.

...