Move all zero values in a big array to its front portion in a Time Efficiency way

You're given a big array with Integral type value, How do you move all zero values within it to the front portion of the array in a Time Efficiency way?

e.g. 0,1,开发者_运维技巧72,3,0,5,9,0,6,51,0,3 ---> 0,0,0,0,1,72,3,5,9,6,51,3

Regards!

---

If you want to keep the order between the other items, loop backwards copying all non-zero items, then fill up with zero items 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 items is not important, you can simply swap zero items with items 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 are O(n).

(Examples in C#, but it should be close enough as it's mostly a question about algorithms...)

---

Although I see Guffa has already given the solution and mine is also essentially doing the same thing (1 pass O(n)). I am sharing it here since i too have written it.

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

---

If the final order is not important, then a simple sort will do the job too.

---

For the case when order is important, a minor optimization. You don't even need the second pass of the array; you can just zero out as you copy the non-zero items to the end. Something like:

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

Where a is the array. O(n), 1 pass.

---

Here's an attempt:

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

---

I have done this way:

Integer array:

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

Call method for move all zero element to end of 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 will help you.

---

We can move all zeros in order of o(n). The idea is to move all the number along with their corresponding positions and put zero after shifting the numbers on the newly available indexes.

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