-
Notifications
You must be signed in to change notification settings - Fork 0
/
Nuts & Bolts Problem.cpp
31 lines (31 loc) · 1.1 KB
/
Nuts & Bolts Problem.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
/**
* @param nuts: a vector of integers
* @param bolts: a vector of integers
* @param compare: a instance of Comparator
* @return: nothing
*/
void __sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare, int l, int r) {
if(l >= r) return;
int i = l, j = r-1;
while(i < j) {
if(compare.cmp(nuts[l], bolts[i]) == 1) i++;
else if(compare.cmp(nuts[l], bolts[j]) == -1) j--;
else swap(bolts[i], bolts[j]);
}
int m = i;
i = l, j = r-1;
while(i < j) {
if(compare.cmp(nuts[i], bolts[m]) == -1) i++;
else if(compare.cmp(nuts[j], bolts[m]) == 1) j--;
else swap(nuts[i], nuts[j]);
}
__sortNutsAndBolts(nuts, bolts, compare, l, m);
__sortNutsAndBolts(nuts, bolts, compare, m+1, r);
}
void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare) {
// write your code here
__sortNutsAndBolts(nuts, bolts, compare, 0, nuts.size());
}
};