找出第 k 大的数字所在的位置

题目：找出第 k 大的数字所在的位置。写一段程序，找出数组中第 k 大小的数，输出数所在的位置。

例如 {2, 4, 3, 4, 7} 中，第一大的数是 7，位置在 4。第二大、第三大的数都是 4，位置在 1、3 随便输出哪一个均可。

先找到第 k 大的数字，然后再遍历一遍数组找到它的位置。所以题目的难点在于如何最高效地找到第 k 大的数。

我们可以通过快速排序、堆排序等高效的排序算法对数组进行排序，然后找到第 k 大的数字。这样总体复杂度为 O(NlogN)。

我们还可以通过二分的思想，找到第 k 大的数字，而不必对整个数组排序。从数组中随机选一个数 t，通过让这个数和其它数比较，我们可以将整个数组分成两部分并且满足：

{x, xx, ..., t} < {y, yy, ...}

在将数组分成两个数组的过程中，我们还可以记录每个子数组的大小。这样我们就可以确定第 k 大的数字在哪个子数组中。

然后我们继续对包含第 k 大数字的子数组进行同样的划分，直到找到第 k 大的数字为止。

平均来说，由于每次划分都会使子数组缩小到原来的 1/2，所以整个过程的复杂度为 O(N)。