Given an array of string, and sequence. Sort the array according to the given sequence.
For example:
String str = "DCBAEECCAAABBAEEE"; String sequence = "ABCDE";
output should be: AAAAABBBCCCDEEEEE
The counting sort like sort algorithms are the ones can be done in O(n).
public static char[] sort(char[] strs, char[] comp){
char[] sorted = new char[strs.length];
int[] count = new int[256];
for(char s : strs){
count[s]++;
}
int index = 0;
for(char c : comp){
int num = count[c];
while(num-->0)
sorted[index++] = c;
}
return sorted;
}
if it is required to sort in place:
Sort the Double linked list in place:
final char[] setOfChars= new char[]{'R', 'G', 'B'};
DLL curr, p;
curr = p = head;
if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}
curr = p = head.pre.pre;
if(p.data == 'B'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.pre;
}
p = p.pre;
}
}
How about Singled LinkedList?
DLL curr = head, p = head;
if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}
while(p != null){
if(p.data == 'G'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}
}
if it is required to sort in place:
public static char[] sort(char[] strs, char[] comp){
int[] count = new int[256];
for(char s : strs){
count[s]++;
}
int index = 0;
for(char c : comp){
int num = count[c];
while(num-->0)
strs[index++] = c;
}
return strs;
}
Sort the Double linked list in place:
/*
* in place sort DLL of Rs, Gs and Bs, so that Rs in front, followed by Gs and Bs
* assume DLL has the sentinel node to separate the head and tail
*/
public static void sortDLL(DLL head, DLL sentinel){final char[] setOfChars= new char[]{'R', 'G', 'B'};
curr = p = head;
//push all R to the front
while(p != sentinel){if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}
//push all B to the back
while(p != sentinel){if(p.data == 'B'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.pre;
}
p = p.pre;
}
}
How about Singled LinkedList?
//here I use DLL node to represent the SLL
//in this case DLL.pre = null
void sortSLL(DLL head){DLL curr = head, p = head;
//push all Rs to the front
while(p != null){if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}
//now all Rs at front and curr points at candidate
//position for next char which is G
//push all Gs to the front
p = curr;while(p != null){
if(p.data == 'G'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}
}
You are right, it is just a counting sort. Easiest one should be the 2nd of your code. I think I thought too much, made the sorting complex. Mine should be O(mn) time complexity.
ReplyDeleteyep, you can pretty much find the solution based on the time complexity the interviewer asks for.
DeleteI also updated the blog with sorting SLL and DLL.
Delete