为复制关键点算法选择轴

Question

我试图了解在数组中查找重复键时如何选择轴。我看到的大多数示例总是选择第一个元素作为轴心，假装这个元素在数组中是重复的。如果不是这样呢？如何正确选择轴？

假设一个数组a[lo... hi]和v分区元素，v=a[lo]。我们还有2个指数gt和lt

• a[lo…lt]小于v

所以我们的想法是从左到右扫描，直到我

• （a[i]

这个想法非常类似于快速排序分区，我想知道在这种情况下如何正确选择枢轴。




Answer 1

选择“轴复制”与否无关。您的算法应该尝试递归地查找重复的元素，直到找到重复的键，它才会停止。

 /*
 *assume that all element are positive, reutrn -1 when there is no duplicate keys
 */
int duplicate_key(int a[], int lo, int ho) { 
 if (ho - lo <= 1) return -1; //no duplicate keys when there is no more than 2 keys
 a[lo ... lt] are less than v
 a[lt ... gt] are equal to v
 a[gt ... hi] are greater than v
 if (gt - lt > 1) return v;
 return max(duplicate_key(a, lo, it), duplicate_key(gt, hi));
}