Given an unsorted array of 0s and 1s, sort the array such that the 0s appear before the 1s.
e.g: A[0,1,1,0] --> A[0,0,1,1].
import java.util.Arrays; public class SortZerosAndOnes { static int[] sortZerosAndOnes(int[] a) { if (a.length < 2) { return a; } int len = a.length; int sum = 0; for(int i = 0 ; i < len ; i++) { if(a[i] == 1) { sum += a[i]; // The result will be the number of 1s in the array a[i] = 0; // Make all the 1s zeros } } // In reverse order place the 1s back into the array for(int i = 0 ; i < sum ; i++) { a[a.length-i-1] = 1; } return a; } public static void main(String[] args) { int[] a = {0,1,0,1,0,1,1,0,1,0,0}; System.out.println(Arrays.toString(sortZerosAndOnes(a))); // OUTPUT: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1] } }
Time Complexity: O(n+m) where:
n - Number of elements in array
m - Number of 1s in the array(assuming the array contains any 1s)
No comments:
Post a Comment