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