Nuts bolts problem
Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts.
Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller. We will give you a compare function to compare nut with bolt.
Using the function we give you, you are supposed to sort nuts or bolts, so that they can map in order.
Example
Given nuts = ['ab','bc','dd','gg']
, bolts = ['AB','GG', 'DD', 'BC']
.
Your code should find the matching of bolts and nuts.
According to the function, one of the possible return:
nuts = ['ab','bc','dd','gg']
, bolts = ['AB','BC','DD','GG']
.
If we give you another compare function, the possible return is the following:
nuts = ['ab','bc','dd','gg']
, bolts = ['BC','AA','DD','GG']
.
So you must use the compare function that we give to do the sorting.
The order of the nuts or bolts does not matter. You just need to find the matching bolt for each nut.
思路:算法比较好想,就是用A最左边的一个pivot, 去sort B,然后用B[index] = A[l] ,去sort A,然后recursion;
partition的method比较难想,tricky的地方就是先要把match的i element拿出来,然后每次右边导到左边,左边导到右边,这样每次都有一个虚位以待的position用来换值;最后把取出来的now 丢到中间;
/**
* public class NBCompare {
* public int cmp(String a, String b);
* }
* You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
* if "a" is bigger than "b", it will return 1, else if they are equal,
* it will return 0, else if "a" is smaller than "b", it will return -1.
* When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
public class Solution {
/**
* @param nuts: an array of integers
* @param bolts: an array of integers
* @param compare: a instance of Comparator
* @return: nothing
*/
public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
if(nuts == null || bolts == null || nuts.length != bolts.length) return;
int n = nuts.length;
qsort(nuts, bolts, 0, n-1, compare);
}
private void qsort(String[] nuts, String[] bolts, int l, int u, NBComparator compare) {
if(l >= u) return;
// use bolts[l] to partition nuts into three pieces;
// nuts[l....p_index-1], nuts[p_index], nuts[p_index+1....u];
int p_index = partition(nuts, bolts[l], l, u, compare);
// bolts[l....p_index-1], bolts[p_index], bolts[p_index+1....u];
partition(bolts, nuts[p_index], l, u, compare);
qsort(nuts, bolts, l, p_index-1, compare);
qsort(nuts, bolts, p_index+1, u, compare);
}
private int partition(String[] strs, String pivot, int l, int u, NBComparator compare) {
String temp;
for(int i = l; i <= u; i++) {
if( (compare.cmp(strs[i], pivot) == 0) || (compare.cmp(pivot, strs[i]) == 0)) {
temp = strs[i];
strs[i] = strs[l];
strs[l] = temp;
}
}
String now = strs[l];
int left = l;
int right = u;
while(left < right) {
while(left < right && (compare.cmp(strs[right], pivot) == 1 || compare.cmp(pivot, strs[right]) == -1)){
right--;
}
strs[left] = strs[right];
while(left < right && (compare.cmp(strs[left], pivot) == -1 || compare.cmp(pivot, strs[left]) == 1)){
left++;
}
strs[right] = strs[left];
}
strs[left] = now;
return left;
}
};
上一篇: ORA-00903 invalid table name
下一篇: Java中抽象类和接口【转】
推荐阅读
-
HDUacm 1000 A + B Problem
-
数据结构(线性结构习题)Problem A: 求集合的交并补集
-
Problem09 求完数
-
洛谷P1919 【模板】A*B Problem升级版(FFT快速傅里叶)
-
Notice: Trying to get property of non-object problem(PHP)解决办法
-
source .bashrc 报错:virtualenvwrapper.sh: There was a problem running the initialization hooks.
-
[Algorithm] 1. A+B Problem
-
No rabbit death problem
-
[转载]—Health Check Reports Problem: Dependency$ p_timestamp mismatch for VALID objects (文档 ID 781959.1)
-
bzoj2301【HAOI2011】Problem b