Move all the null values ​​in the large array to its front in Time Efficiency mode

Question

You are given a large array with a value of type Integral, how do you move all zero values ​​inside it to the front of the array using the Time Efficiency method?

eg. 0,1,72,3,0,5,9,0,6,51,0,3 ---> 0,0,0,0,1,72,3,5,9,6,51,3

Hello!

Answer 1

If you want to maintain order between other elements, back up all non-zero elements, and then fill in the zero positions at the beginning:

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;

If the order of the elements is not important, you can simply replace the null elements with the elements at the beginning of the array:

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

Both algorithms: O (n).

( #, , ...)

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

, .

Answer 4

, , . ; . - :

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++;
    } 
}

a - . O (n), 1 .

Answer 5

:

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 6

:

Integer :

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

Call the method to move the entire null element to the end of the array:

moveAllZerosElementToEndOfArray(mArray);

Add this method:

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]);
        }
    }

Hope this helps you.

Answer 7

We can move all zeros in order o (n). The idea is to move the whole number together with their corresponding positions and put zero after shifting the numbers at the newly available indices.

   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;
        }