请教这道 Lintcode 的 Nuts & Bolts problem

http://www.lintcode.com/en/problem/nuts-bolts-problem/#

基本思路很简单，由于compare规定只能按（nut, bolt）的顺序放， 先从nut里选一个做pivot，按此pivot与bolts array进行比较并且进行partition; 而后返回pivot element的index，代表对应原先选择的nut的bolt，并且以此元素回到nuts array里面进行partition； 最后递归处理左右两边。

但是这题在第六个test case总挂，测试了好多遍也不清楚为什么，向论坛里各位请教下，谢谢！

1. /**
   
2. * public class NBCompare {
   
3. *     public int cmp(String a, String b);
   
4. * }
   
5. * You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
   
6. * if "a" is bigger than "b", it will return 1, else if they are equal,
   
7. * it will return 0, else if "a" is smaller than "b", it will return -1.
   
8. * When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
   
9. */
   
10. public class Solution {
    
11.     /**
    
12.      * @param nuts: an array of integers
    
13.      * @param bolts: an array of integers
    
14.      * @param compare: a instance of Comparator
    
15.      * @return: nothing
    
16.      */
    
17.     public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
    
18.         /*
    
19.         if(nuts[0].equals("ab")){
    
20.             for(String nut : nuts){
    
21.                 for(String bolt : bolts){
    
22.                     if(compare.cmp(nut, bolt) == 0)
    
23.                         System.out.println(nut + " matches " + bolt);
    
24.                 }
    
25.             }
    
26.         }
    
27.         */
    
28.         sortSubArray(nuts, bolts, 0, nuts.length - 1, compare);
    
29.     }
    
30.    
    
31.     private void sortSubArray(String[] nuts, String[] bolts, int start, int end, NBComparator compare){
    
32.         if(start >= end) return;
    
33.         
    
34.         int pivot = sortBolts(nuts[start], bolts, start, end, compare);
    
35.      
    
36.         sortNuts(nuts, bolts[pivot], start, end, compare);
    
37.         
    
38.         sortSubArray(nuts, bolts, start, pivot - 1, compare);
    
39.         sortSubArray(nuts, bolts, pivot + 1, end, compare);
    
40.         
    
41.         return;
    
42.     }
    
43.    
    
44.     private int sortBolts(String nut, String[] bolts, int start, int end, NBComparator compare){
    
45.         
    
46.         int left = start;
    
47.         int right = end;
    
48.         
    
49.         while(left < right){
    
50.             while(left < right && compare.cmp(nut, bolts[left]) < 0){
    
51.                 left++;
    
52.             }
    
53.             while(left < right && compare.cmp(nut, bolts[right]) > 0){
    
54.                 right--;
    
55.             }
    
56.             
    
57.             if(left < right) swap(bolts, left, right);
    
58.         }
    
59.         
    
60.         /*
    
61.         System.out.println("Current Bolts: ");
    
62.         for(String bolt : bolts){
    
63.             System.out.print(bolt + " ");
    
64.         }
    
65.         for(String bolt : bolts){
    
66.             System.out.print(compare.cmp(nut, bolt) + " ");
    
67.         }
    
68.         System.out.println("Given nut: " + nut);
    
69.         System.out.println("Pivot index: " + left);
    
70.         */
    
71.         for(int i = start; i <= end; i++ ){
    
72.             if(compare.cmp(nut, bolts[i]) == 0) left = i;
    
73.         }
    
74.         return left;
    
75.     }
    
76.    
    
77.     private void sortNuts(String[] nuts, String bolt, int start, int end, NBComparator compare){
    
78.         int left = start;
    
79.         int right = end;
    
80.         
    
81.         while(left < right){
    
82.             while(left < right && compare.cmp(nuts[left], bolt) > 0){
    
83.                 left ++;
    
84.             }
    
85.             while(left < right && compare.cmp(nuts[right], bolt) < 0){
    
86.                 right --;
    
87.             }
    
88.             if(left < right) swap(nuts, left, right);
    
89.         }
    
90.         
    
91.         /*
    
92.         System.out.println("Current Bolts: ");
    
93.         for(String nut : nuts){
    
94.             System.out.print(nut + " ");
    
95.         }
    
96.         for(String nut : nuts){
    
97.             System.out.print(compare.cmp(nut, bolt) + " ");
    
98.         }
    
99.         System.out.println("Given bolt: " + bolt);
    
100.         System.out.println("Pivot index: " + left);
     
101.         */
     
102.         
     
103.         
     
104.         return;
     
105.     }
     
106.    
     
107.     private void swap(String[] array, int a, int b){
     
108.         String temp = array[a];
     
109.         array[a] = array[b];
     
110.         array[b] = temp;
     
111.     }
     
112. };
     

复制代码

第 71 - 73 行原先没有，我在测试的时候加了进去想看看是不是返回的index有问题，实际跑的时候请拿掉

我的思路和你类似，但是我的在第5个挂掉，感觉可能是 lintcode 方面的问题？

billryan 发表于 2015-7-30 22:10
我的思路和你类似，但是我的在第5个挂掉，感觉可能是 lintcode 方面的问题？

因为test case很大而且不是按照字面字母对应，在那个test case上具体哪里出了问题我也不清楚。

不过试了好几种不同的partition写法依然在同一个test case上挂让人想不通啊。

mnmunknown 发表于 2015-7-30 23:53
因为test case很大而且不是按照字面字母对应，在那个test case上具体哪里出了问题我也不清楚。

不过试 ...

同样的思路我用 Python 和 C++写的过了，见 https://github.com/billryan/algo ... nd_bolts_problem.md

不知道楼主ac木有啊？ 我也卡在这里了。

chenjunren0406 发表于 2015-8-4 13:53
不知道楼主ac木有啊？ 我也卡在这里了。

没，我现在倾向于认为这题的java test case有问题。。。等待哪位java ac的消息

chenjunren0406 发表于 2015-8-4 13:53
不知道楼主ac木有啊？ 我也卡在这里了。

一行代码没改，前两天再跑就ac了，看来是test case有问题

感谢楼组提醒，我刚刚去提交了，也ac了。

我做这道题的时候也是有时可以通过，有时说超时，用的是c++。

[i][i]

1. class Solution {
   
2. public:
   
3.     using CompareResult = enum { SMALLER = -1, EQUAL = 0,
   
4.                                  BIGGER = 1, REVERSED = 2 };
   
5.     void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare)
   
6.     {
   
7.         if (nuts.size() != bolts.size() || nuts.empty() || bolts.empty())
   
8.         {
   
9.             return;
   
10.         }
    
11.         quick_sort(nuts, bolts, 0, bolts.size() - 1, compare);
    
12.     }
    
13.    
    
14.     int partition(string pivot_other, vector<string> &targets, int l, int r, Comparator compare)
    
15.     {
    
16.         
    
17.         for (int i = l; i <= r; i++)
    
18.         {
    
19.             if (compare.cmp(pivot_other, targets) == 0 || compare.cmp(targets, pivot_other) == 0)
    
20.             {
    
21.                 swap(targets, targets[l]);
    
22.                
    
23.                 break;
    
24.             }
    
25.         }
    
26.         string pivot = targets[l];
    
27. 
    
28.         while (l < r)
    
29.         {
    
30.             while
    
31.             (
    
32.                 l < r &&
    
33.                 (compare.cmp(pivot_other, targets[r]) == BIGGER ||
    
34.                  (compare.cmp(pivot_other, targets[r]) == REVERSED &&
    
35.                   compare.cmp(targets[r], pivot_other) == SMALLER)
    
36.                  )
    
37.             )
    
38.             {
    
39.                 r--;
    
40.             }
    
41.             targets[l] = targets[r];
    
42. 
    
43.             while
    
44.             (
    
45.                 l < r &&
    
46.                 (compare.cmp(pivot_other, targets[l]) == SMALLER ||
    
47.                 (compare.cmp(pivot_other, targets[l]) == REVERSED &&
    
48.                  compare.cmp(targets[l], pivot_other) == BIGGER)
    
49.                 )
    
50.             )
    
51.             {
    
52.                 l++;
    
53.             }
    
54.             targets[r] = targets[l];
    
55.         }
    
56.         targets[l] = pivot;
    
57.         return l;
    
58.     }
    
59.    
    
60.     void quick_sort(vector<string> &nuts, vector<string> &bolts, int l, int r, Comparator compare)
    
61.     {
    
62.         if (l >= r)
    
63.         {
    
64.             return;
    
65.         }
    
66.         string pivot_from_bolts = bolts[l];
    
67.         int idx = partition(pivot_from_bolts, nuts, l, r, compare);
    
68.         
    
69.         string pivot_from_nuts = nuts[idx];
    
70.         partition(pivot_from_nuts, bolts, l, r, compare);
    
71.         
    
72.         quick_sort(nuts, bolts, l, idx - 1, compare);
    
73.         quick_sort(nuts, bolts, idx + 1, r, compare);
    
74.     }
    
75. };

复制代码

// reference:　https://github.com/kamyu104/LintCode/blob/master/C++/nuts-bolts-problem.cpp[/i][/i]