Переместите все нулевые значения в большом массиве в его переднюю часть способом повышения эффективности времени

Question

Вам дан большой массив со значением типа Integral. Как вы перемещаете все нулевые значения в нем в переднюю часть массива способом эффективности времени?

например, 0,1,72,3,0,5,9,0,6,51,0,3 ---> 0,0,0,0,1,72,3,5,9,6,51,3

Привет! * * 1005

Answer 1

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

int source = arr.Length - 1;
int dest = arr.Length - 1;
while (source >= 0) {
  if (arr[source] != 0) {
    arr[dest--] = arr[source];
  }
  source--;
}
while (dest >= 0) arr[dest--] = 0;

Если порядок элементов не важен, вы можете просто поменять нулями элементы с элементами в начале массива:

int dest = 0;
for (int source = 0; source < arr.Length; source++) {
  if (arr[source] == 0) {
    arr[source] = arr[dest];
    arr[dest++] = 0;
  }
}

Оба алгоритма O (n).

(Примеры в C #, но это должно быть достаточно близко, так как это в основном вопрос об алгоритмах ...)

Answer 2

Хотя я вижу, что Гуффа уже дал решение, и мое, по сути, тоже делает то же самое (1 проход O (n)).Я делюсь этим здесь, так как я тоже написал это.

int counter = arr.length - 1;        
int swapPosition = arr.length - 1;
while (counter >= 0) {
    if(arr[counter] != 0){
        swap(arr, counter, swapPosition);
        swapPosition--;
    }
    counter--;
}

swap(int[] arr, int indx1, int indx2){
    int t = arr[indx1];
    arr[indx1] = arr[indx2];
    arr[indx2] = t;
}

Answer 3

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

int counter = 0;
for (int i = a.length-1; i >= 0; i--) {
    if (a[i] != 0){

    a[a.length-1-counter] = a[i];
    a[i] = 0;
    counter++;
    } 
}

Где это массив. O (n), 1 проход

Answer 4

Если окончательный порядок не важен, то сработает и простая сортировка.

Answer 5

Я сделал так:

Целочисленный массив:

int [] mArray = {0,3,6,0,3,9,5,2,0};

Вызов метод для перемещение всех нулевых элементов в конец из массива :

moveAllZerosElementToEndOfArray(mArray);

Добавить этот метод:

private void moveAllZerosElementToEndOfArray(int arr[])
    {
        int count = 0;  // Count of non-zero elements
        // Traverse the array. If element encountered is non-zero, then
        // replace the element at index 'count' with this element
        for (int i = 0; i < arr.length; i++)
            if (arr[i] != 0)
                arr[count++] = arr[i]; // here count is incremented

        // Now all non-zero elements have been shifted to front and 'count' is
        // set as index of first 0. Make all elements 0 from count to end.
        while (count < arr.length)
            arr[count++] = 0;

        for (int i = 0; i < arr.length; i++) {
            Log.i(TAG, ""+arr[i]);
        }
    }

Надеюсь, это поможет вам.

Answer 6

Вот попытка:

public class MoveAllZeroToRight {

/**
 * @param args
 * You are given an integer array which contains some zeros. 
 * Move the zeros to the right side of the array with minimum number of swaps. 
 * The order of the original array can be destroyed.
 */
 public static void main(String[] args) {
    int[] a = {1,3,0,2,6,0,0,3,0,4,0,8};
    a = moveAllZerosToRight(a);
    for(int i=0;i<a.length;i++)
        System.out.print(a[i]+" ");
 }
 public static int[] moveAllZerosToRight(int[] a){
    int i=0;
    int j=a.length-1;
    while(i<j){
        if(a[i]==0 && a[j]!=0){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;j--;
        }
        else{
            if(a[i]!=0)
                i++;
            if(a[j]==0)
                j--;
        }
    }
    return a;
 }
}

Answer 7

Мы можем перемещать все нули в порядке o (n).Идея состоит в том, чтобы переместить все числа вместе с соответствующими им позициями и поставить ноль после смещения чисел на вновь доступных индексах.

   private static int[] reArrangeNonZeroElementInBack(int arr[]) {
            int count = arr.length - 1;
            int len = arr.length;
            if (len == 0)
                return arr;
            for (int i = len - 1; i >= 0; i--) {
                if (arr[i] != 0) {
                    arr[count--] = arr[i];

                }
            }
            for (; count >= 0;) {
                arr[count--] = 0;``

            }
            return arr;
        }