Given a array of 0's,1's and 2's arrange in a way that all 0's come first, then 1's then 2's.
Method 1: (By using sorting)
void arrange(int []array){
if(array == null || array.length == 0)
return;
java.util.Arrays.sort(a);
}
Time Complexity : O(NlogN)
Method 2: (by counting the 0s, 1s and 2s)
void arrange(int []array){
if(array == null || array.length == 0)
return;
int countZeros = 0;
int countOnes = 0;
int countTwos = 0;
for(int i = 0; i < a.length; i++){
if(a[i] == 0)
countZeros++; //count number of zero
else if(a[i] == 1)
countOnes++; //count number of one
else if(a[i] == 2)
countTwos++; // count number of two
}
for(int i = 0; i < countZeros; i++)
a[i] = 0; //write zero to array
for(int i = countZeros; i <a.length-countTwos; i++)
a[i] = 1; //write one
for(int i = countZeros+countOnes; i < a.length; i++)
a[i] = 2; //write two
}
Time Complexity : O(N)
Method 3 : (By using Dutch flag algorithm)
For Dutch Flag Algorithm, click here
void arrange(int []a){
if(array == null || array.length == 0)
return;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
//Traverse the array once to pickup min and max values
for(int i = 0; i < a.length; i++){
if(a[i] > max)
max = a[i];
if(a[i] < min)
min = a[i];
}
int p = 0, q = a.length - 1;
int temp; //for swapping values
for(int i = 0; i < q; i++){
if(a[i] == min){ //place the min value at the lowest position
temp = a[p];
a[p] = a[i];
a[i] = temp;
p++;
}
if(a[i] == max){ //place the max value at the highest position
temp = a[q];
a[q] = a[i];
a[i] = temp;
q--;
i--;
}
}
}
Time Complexity : O(N)
Method 1: (By using sorting)
void arrange(int []array){
if(array == null || array.length == 0)
return;
java.util.Arrays.sort(a);
}
Time Complexity : O(NlogN)
Method 2: (by counting the 0s, 1s and 2s)
void arrange(int []array){
if(array == null || array.length == 0)
return;
int countZeros = 0;
int countOnes = 0;
int countTwos = 0;
for(int i = 0; i < a.length; i++){
if(a[i] == 0)
countZeros++; //count number of zero
else if(a[i] == 1)
countOnes++; //count number of one
else if(a[i] == 2)
countTwos++; // count number of two
}
for(int i = 0; i < countZeros; i++)
a[i] = 0; //write zero to array
for(int i = countZeros; i <a.length-countTwos; i++)
a[i] = 1; //write one
for(int i = countZeros+countOnes; i < a.length; i++)
a[i] = 2; //write two
}
Time Complexity : O(N)
Method 3 : (By using Dutch flag algorithm)
For Dutch Flag Algorithm, click here
void arrange(int []a){
if(array == null || array.length == 0)
return;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
//Traverse the array once to pickup min and max values
for(int i = 0; i < a.length; i++){
if(a[i] > max)
max = a[i];
if(a[i] < min)
min = a[i];
}
int p = 0, q = a.length - 1;
int temp; //for swapping values
for(int i = 0; i < q; i++){
if(a[i] == min){ //place the min value at the lowest position
temp = a[p];
a[p] = a[i];
a[i] = temp;
p++;
}
if(a[i] == max){ //place the max value at the highest position
temp = a[q];
a[q] = a[i];
a[i] = temp;
q--;
i--;
}
}
}
Time Complexity : O(N)
No comments:
Post a Comment