Java - перестроить массив int так, чтобы все отрицательные числа приходили перед позитивистскими числами

Question

Я пытаюсь написать mehtod, который принимает массив из int и затем переупорядочивает числа в массиве, чтобы первые отрицательные числа были первыми. Массив не нужно сортировать в любом случае. Единственное требование состоит в том, что решение должно быть линейным и не использовать дополнительный массив.

Пример: Входной сигнал: {1, -5, 6, -4, 8, 9, 4, -2} Выход: {-5, -2, -4, 8, 9, 1, 4, 6}

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

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

Мой код:.

public static void separateArray(int[] numbers) { 
    int i = 0; 
    int j = numbers.length-1; 
    while(i<j){ 

     if(numbers[i] > 0){ 
      int temp; 
      temp = numbers[j]; 
      numbers[j] = numbers[i]; 
      numbers[i] = temp; 
      System.out.println(Arrays.toString(numbers)); 
     } 

     i++; 
     j--; 
    } 
} 

Любая помощь очень ценится (была бы очень признательна, если вы могли бы также определить, что именно «линейный раствор» Я искал по всему интернету и нашел очень неопределенные explainations но не четкое определение). Благодаря!

EDIT: Решенный!

Final Код:

public static void separateArray(int[] numbers) { 
    int i = 0; 
    int j = numbers.length-1; 
    while(i<j){ 

     if(numbers[i] >= 0 && numbers[j] < 0){ 
      int temp; 
      temp = numbers[j]; 
      numbers[j] = numbers[i]; 
      numbers[i] = temp; 
     } 

     if(numbers[i] < 0){ 
      i++; 
     } 

     if(numbers[j] >= 0){ 
      j--; 
     } 
    } 
} 

Answer 1

Вам нужно только изменить одну строку, чтобы получить (в основном) работу. Но вам нужно изменить две строки, чтобы правильно обрабатывать нули во входе. Я выделил оба этих минимально необходимых изменений с «FIXME» комментарии ниже:

public static void separateArray(int[] numbers) { 
    int i = 0; 
    int j = numbers.length-1; 
    while(i<j){ 
     if(numbers[i] > 0){ // FIXME: zero is not a "negative number" 
      int temp; 
      temp = numbers[j]; 
      numbers[j] = numbers[i]; 
      numbers[i] = temp; 
     } 
     i++; // FIXME: only advance left side if (numbers[i] < 0) 
     j--; 
    } 
} 

Answer 2

Линейный раствор представляет собой раствор с run-time complexity Big-Oh (п) также отмечен как O (п), другими словами, вы должны перебрать весь массив только один раз. Для сортировки за линейное время, вы можете попробовать один из следующих алгоритмов сортировки:

• Pigeonhole sort
• Counting sort
• Radix sort

Answer 3

Ваш подход с двумя указателями, i и j является хорошим началом.

Подумайте о инварианта цикла, что вы сразу же настроить (бессодержательно):

• элементов в диапазоне 0 (включительно) до i (эксклюзив) отрицательны;
• Элементы в диапазоне j (исключительно) до numbers.length (эксклюзивные) неотрицательны.

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

• Если i < numbers.length и numbers[i] < 0, вы можете увеличить i на 1;
• Если j >= 0 и numbers[j] >= 0, вы можете уменьшить j на 1;
• Если i < numbers.length и j >= 0, то numbers[i] >= 0 и numbers[j] < 0. Поменяйте их.

Если вы продолжайте применять эту стратегию до i == j + 1, то вы в конечном итоге с желаемой ситуации, что:

• numbers[a] < 0 for a in [0..i)
• numbers[a] >= 0 for a in (j..numbers.length), также пишется как numbers[a] >= 0 for a in (i-1..numbers.length), также пишется как numbers[a] >= 0 for a in [i..numbers.length).

Итак, вы разделили массив так, чтобы все отрицательные числа на левой стороне i -го элемента, и все неотрицательные числа в или справа от i -го элемента.

Надеюсь, этот алгоритм должен быть легко следовать и, следовательно, реализовать.

Answer 4

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

Answer 5

//Move positive number left and negative number right side 

public class ArrangeArray { 
    public static void main(String[] args) { 
     int[] arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4 }; 
     for (int i = 0; i < arr.length; i++) { 
      System.out.print(" " + arr[i]); 
     } 
     int temp = 0; 
     for (int i = 0; i < arr.length; i++) { 
      // even 
      if (arr[i] < 0) { 
       for (int j = i + 1; j < arr.length; j++) { 
        if (arr[j] > 0) { 
         arr[j] = arr[i] + arr[j]; 
         arr[i] = arr[j] - arr[i]; 
         arr[j] = arr[j] - arr[i]; 
         break; 
        } 
       } 
      } 
     } 
     System.out.println(""); 
     for (int i = 0; i < arr.length; i++) { 
      System.out.print(" " + arr[i]); 
     } 
    } 
}