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