谁能解释一下我做错了什么?我想找到第 k 个最小的元素,但出了点问题)
例子:我有未排序的数组 int[] uA = {2, 9, 4, 13, 11, 7, 8}; 我将“9”作为一个主元元素,在第一次迭代 partiting(快速排序)之后,我将得到这个数组 {2、8、4、7、11、13、9}。中间指针将显示在“11”处。这到底是什么意思?并非所有元素都适合 11 大于 11。而且 11 根本不在“正确的位置”。但是,例如,我想返回第 5 个最小的元素 (11)。
最佳答案
枢轴不在正确的位置,你应该在分区结束时将枢轴放在正确的位置,以找出枢轴的位置。 (你真的不需要关心中间的元素)然后你可以使用这些信息来计算第K小的元素。假设主元位于分区结束时的第 x 个索引处;
K = x => pivot is the right answer
K < x => the answer is in the left partition, search left partition
K > x => the answer is in the right partition, search right partition
关于algorithm - 找到第 K 个最小的元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13185508/