Альтернативное положительное отрицательное число в массиве

Question

Учитывая массив положительных и отрицательных чисел (без нулей), я должен упорядочить их таким образом, чтобы положительное и отрицательное числа были упорядочены последовательно. Число положительных и отрицательных чисел числа не могут быть равны, т. е. если в положительном числе (или отрицательном) не осталось положительного числа, тогда все остальные отрицательные числа (или положительные) добавляются к концу массива. Порядок важен, т. е. входной массив равен {2, - 1, -3, -7, -8,9,5, -5, -7}, тогда выходной массив должен быть {2, -1,9, -3,5, -7, -8, -5, -7}. Код выполняется в O (n) без использования другого массива.

Это мое решение в java, я снова тестирую его на несколько случаев, и он работает. Однако я не уверен, что это выполняется в O (n) времени. В принципе, я сначала подсчитываю число положительных и отрицательных чисел. то у меня есть два индекса i = 0 и j = 1. j всегда на 1 шаг вперед i. Оттуда я продолжаю проверять, является ли число в i положительным, а j отрицательным, если это не так, я буду перебирать массив, пока не найду следующий положительный/отрицательный для правильной позиции и переместил бы его в правильное положение.

Любое предложение очень ценится. Благодаря!

//array of negative and positive, arrange them so that positive number follow by negative 
// if no pos or neg left, the rest append to the array. 
//should be O(n) no additional array 
public static void alter(int[] a) { 
     int pos = 0; 
     int neg = 0; 
     int index = 0; 
     while(c <a.length){ 
      if(a[index] > 0){ 
       pos++; 
      } 
      else neg++;    
      index++; 
     } 

     int i = 0; 
     int j = 1; 
     int temp = 0; 
     //run until no more positive number or negative number 
     while(pos >0 && neg > 0){ 
      // 
      if(a[i] > 0){ 
       pos--; 
       if(a[j] < 0){ 
        i += 2; 
        j += 2;     
        neg--; 
       }else // a[j] > 0 
        { 
         while(a[j] > 0){ 
         j++; 
         } 
         //a[j] < 0 
        neg--; 
        //move that number to the appropriate place 
        while(j > i){ 
         temp = a[j]; 
         a[j] = a[j -1]; 
         a[j-1] = temp; 
         j--;     
        }// end while 
        i += 2; 
        j +=2 ; 
        }   
      }else // a[i] < 0 
       { 
       while(a[i] < 0){ 
        i++; 
       } 
       //a[i] > 0 
       //move that number to the appropriate place 
       while(i > (j -1)){ 
        temp = a[i]; 
        a[i] = a[i-1]; 
        a[i-1] = temp; 
        i--; 
       } 

      } //end else  
     } 

    } 

Answer 1

Однако, я не уверен, если это запустить в O(n) время

Я не думаю, что он работает в O(n). В тот момент, когда вам нужно «найти следующий правильный элемент и переместить его в нужное место», вам необходимо установить

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

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

Answer 2

Да, это можно сделать в O (n).

Предположим, что c - текущее положение. И a [c] - положительное число.

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

2) Set j := i;

3) не Приращение J в сторону конца массива до J указывает на номер с разыскиваемого знаком (в данном случае - отрицательный).

4) Swap a[i] with a[j].

5) Set c := j;

6) Set j := c + 1;

На каждом шаге вы всегда увеличиваем я или J или гр. Никогда не уменьшайте. Переменная i может быть увеличена не более, чем n раз. То же самое относится к j и c.

Максимальное количество приращений: 3n ~ O (n).

Answer 3

PFB мой код. Если мы будем использовать Stack, это облегчит нашу задачу.

public class AlternatePosNeg { 
public static void main(String[] args) { 
    int arr[] = { 2, -1, -3, -7, -8, 9, 5, -5, -7 }; 

    Stack<Integer> pos = new Stack<>(); 
    Stack<Integer> neg = new Stack<>(); 

    int i; 

    for (i = 0; i < arr.length; i++) { 
     if (arr[i] > 0) { 
      pos.push(arr[i]); 
     } else { 
      neg.push(arr[i]); 
     } 
    } 

    int tempArr[] = new int[arr.length]; 

    i = 0; 

    int sizePos = pos.size(); 
    int sizeNeg = neg.size(); 

    while (i < tempArr.length) { 
     if (sizePos > sizeNeg) { 
      if (pos.size() > 0) { 
       tempArr[i] = pos.pop(); 
      } 
      if (neg.size() > 0) { 
       tempArr[i + 1] = neg.pop(); 
       i++; 
      } 
     } else { 
      if (neg.size() > 0) { 
       tempArr[i] = neg.pop(); 
      } 
      if (pos.size() > 0) { 
       tempArr[i + 1] = pos.pop(); 
       i++; 
      } 
     } 

     i++; 
    } 

    for (int no : tempArr) { 
     System.out.print(no + " "); 
    } 
} 

}