题目:螺丝和螺帽。(G. J. E. Rawlins) 假设有 N 个螺丝和 N 个螺帽混在一堆,你需要快速将它们配对。一个螺丝只会匹配一个螺帽,一个螺帽也只会匹配一个螺丝。你可以试着把一个螺丝和一个螺帽拧在一起看看谁大了,但不能直接比较两个螺丝或者两个螺帽。给出一个解决这个问题的有效方法。
#include<iostream>
using namespace std;
void print(int *a, int *b){
for(int i = 0;i < 5;++i){
cout << a[i] << " ";
}
cout << endl;
for(int i = 0;i < 5;++i){
cout << b[i] << " ";
}
cout << endl;
}
int partition(int* s, int* m, int lo, int hi){
int i = lo, j = hi + 1;
int m_pivot = s[lo];
while(true){
while(s[++i] < m_pivot) if(i == hi) break;
while(m_pivot < s[--j]) if(j == lo) break;
if(i >= j) break;
swap(s[i], s[j]);
}
swap(s[lo], s[j]);
print(m, s);
i = lo, j = hi + 1;
int s_pivot = m_pivot;
while(true){
while(m[++i] < s_pivot) if(i == hi) break;
while(s_pivot < m[--j]) if(j == lo) break;
if(i >= j) break;
swap(m[i], m[j]);
}
swap(m[lo], m[j]);
print(m, s);
cout << endl;
return j;
}
void sort(int* m, int* s, int lo, int hi){
if(hi <= lo) return;
int j = partition(m, s, lo, hi);
sort(m, s, lo, j - 1);
sort(m, s, j + 1, hi);
}
void sort(int* m, int* s, int size){
sort(m, s, 0, size);
}
int main(){
int a[5] = {1, 3, 2, 5, 4};
int b[5] = {3, 4, 2, 5, 1};
sort(a, b, 5);
for(auto i : a){
cout << i << " ";
}
cout << endl;
return 0;
}
解法:
螺帽螺丝相互分区即可使螺丝螺帽分别有序。
具体步骤:
用螺丝把螺母分区,得到三个区:
A1:小于螺丝;
A2:等于螺丝,含一个螺母;
A3:大于螺丝。
用 A2 的螺母将螺丝分区,得到三个区:
B1:小于螺母;
B2:等于螺母;
B3:大于螺母。
A1与B1对应,A3与B3对应,继续对A1与B1 和 A3与B3使用上述算法,直到所有区的螺丝与螺母数目为一。
**
但是代码分区过程中会将螺母与螺丝混淆,**
体现在代码上就是 m 与 s 中的某些元素会交换,但代码中并没有交换 m s 的语句。
大家能帮我找出来哪里错了吗