Переставляя массив таким образом, чтобы положительные и отрицательные элементы в альтернативных положениях


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

Мы должны изменить этот массив таким образом, что все положительные и отрицательные элементы в альтернативных положениях, а также соответствующий приказ должен быть сохранен. Н т. е. размер массива может быть: 1<=Н<=\10$^6\$ . Никакие дополнительные данные структуры могут быть использованы

Вход:

1 2 3 -1 -2 -3  

Выход:

1 -1 2 -2 3 -3  

Мой код был принят, но он превысил лимит времени для дела. Как я могу сделать мой код более эффективным за счет сокращения времени сложность?

Мой код:

import java.util.*;
 class A{
 public static void main(String args[])
 {
     Scanner s=new Scanner(System.in);
     int n=s.nextInt();
     int a[]=new int[n];
     for(int i=0;i<n;i++)
         a[i]=s.nextInt();
     rearrange(a);
     for(int i=0;i<n;i++)
         System.out.print(a[i]+" ");
 }

public static void rotateright(int a[],int l,int r)
{
    int temp=a[r];
    for(int i=r;i>l;i--)
    {
        a[i]=a[i-1];
    }
    a[l]=temp;
}
public static void rearrange(int a[])
{
    int n=a.length;
    int i=0,j=0;
    while(i<n)
    {   
        if(i%2==0)    //even index should have positive element
        {
            if(a[i]>0)     //already positive
                i++;
            else               //for negative
            {
                j=i+1;
                while(j<n)      //finding next positive
                {
                    if(a[j]>0)
                        break;
                    j++;
                }
                rotateright(a,i,j);    //making even index positive
                i++;
            }
        }
        else            //odd index should have negative element
        {
            if(a[i]<0)   //already negative
                i++;
            else           //for positive
            {
                j=i+1;
                while(j<n)          //finding next negative
                {
                    if(a[j]<0)
                        break;
                    j++;
                }
                rotateright(a,i,j);     //making odd index negative
                i++;
            }
        }
    }
}
}


Комментарии
3 ответа

Худшем случае

Представляю худшем случае помогает понять проблемы.
Тест не возможно использует массив размера n, содержащий N/2 положительные числа, далее следуют N/2 отрицательные числа (или наоборот).

Текущая реализация

Обратите внимание, что когда вы найдете нужный элемент на своем месте, вы не повторяя дважды через индексы, пока вы не найдете правильный элемент: один раз два нашли свою позицию, другой, чтобы переместить все элементы между ними.
Вы можете совместить обе операции в одну. До сих пор этот алгоритм напоминает сортировка вставками. Это будет квадратичная, в худшем случае, что я описал (точнее, (Н/2)^2).

Используя дополнительное пространство

Один эффективный способ решить это, чтобы создать правильный массив с самого начала. Это требует O(1) дополнительного пространства.
Создать 3 массива: один для буфера положительных чисел, другой для буфера отрицательные числа, и 3-ий с конечным результатом.

При чтении из stdin:


  • Место в 3-й массив, если он соответствует позиции, в противном случае храните его в соответствующий массив;

  • Если номер совпадает, попробовать в использовании номеров, сохраненных в положительных/отрицательных чисел массивов, чтобы сохранить подачу 3-й массив (используя ФИФО).

Что мы делаем, - это по существу слияние 3 сортированных массивов: стандартный ввод, массив положительных чисел и массив с отрицательными числами.

Это должно работать линейно, требующих 2 записи в ряд из Место.

1
ответ дан 8 февраля 2018 в 08:02 Источник Поделиться

Производительности

Я вижу два медленных элементов в этом коде:


  • Найти следующий указатель, чтобы повернуть суб-массива

  • Вращающихся массива

Текущая реализация начинается поиск следующего индекса положительного или отрицательного элемента всегда от текущего индекса.
Это не оптимально.
Рассмотрим пример ввода, если массив начинается с \$n чисел\$ негативные последующим \Н $\$ положительных чисел.
Как сканировать слева направо, на каждом шагу вам искать от почти начала до почти полпути, выполнить вращение,
потом снова поиск. Для такого ввода, поиска квадратичная.

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

Как для вращающихся массива,
Я боюсь, что не будет волшебной пули без использования дополнительной памяти.
Небольшое улучшение возможно путем замены ручного вращения с System.arraycopy:

int temp = arr[right];
System.arraycopy(arr, left, arr, left + 1, right - left);
arr[left] = temp;

Не повторяйся

В rearrange,
i++ происходит в конце всех ветвей исполнения.
Лучше было бы извлечь i++ до конца наружное whileпетли.
Таким образом, вы не можете случайно забыть его в одной из веток.

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

В Java, переменные блок-уровня.
Так что вам не нужно инициализировать int j впереди,
лучше сделать это в наименьшем объеме.
(Обратите внимание, что с моим предложением выше, чтобы отслеживать последние известные положительные и отрицательные значения, этот момент является спорным, поскольку int nextNegativeIndex и int nextPositiveIndex надо будет заявить в верхней части функции, чтобы отслеживать на протяжении всего цикла.)

Стиль

Это хорошо, чтобы использовать описательные имена переменных,
как я сделал выше в переписать rotaterightметод.
Кроме того, общие конвенции в Java является использование camelCase для способ и имена переменных,
так rotateRight было бы лучше.

Общей конвенции в Java является место открытия { на одной строке в заявлении.
И рекомендуется всегда использовать { ... } С if, whileзаявления.
Вот так, и я предлагаю принять этот стиль написания:

j = i + 1;
while (j < n) {
if (a[j] > 0) {
break;
}
j++;
}
rotateright(a, i, j);
i++;

1
ответ дан 10 февраля 2018 в 07:02 Источник Поделиться

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

Идея в том, чтобы пройти через массив ровно один раз и сделать 1 из 2 вещей:
1) проверить, если это неуместно пункт
2) Если у нас уже есть из элемента, проверьте, если новый надо ставить, что ранее нашли место.

Это приводит к следующему решению:

public static void rearrange(int arr[]){
int outOfPlace = -1;
for(int index = 0; index < arr.length; index ++){
if(outOfPlace == -1){ //looking for the first out of place index
if (((arr[index] < 0) && (index % 2==0))
|| ((arr[index] >= 0) && (index % 2)==1)) {
outOfPlace = index;
}
} else { // previously found an out of place index and now looking what to put there
if ((((outOfPlace % 2) == 0) && (arr[index] >= 0))
|| (((outOfPlace % 2) == 1) && (arr[index] < 0))) {
rotateright(arr, outOfPlace, index);
if(outOfPlace + 1 < index){
outOfPlace += 2;
} else {
outOfPlace = -1;
}
}
}
}
}

Обратите внимание, что на Шаге 2 после замены элемента, мы знаем, что следующий "неправильный" элемент или 2 места и далее (если это список всех положительных/отрицательных чисел) или нажмите текущем месте и вернитесь к шагу 1.


Если это все еще слишком медленно у меня нет идей.

0
ответ дан 8 февраля 2018 в 02:02 Источник Поделиться