题目地址：

https://www.lintcode.com/problem/find-the-rank/description

给定一系列学生的各科分数数组$A$，要求返回总成绩第$k$高的学生的下标。

思路是快速选择。总成绩第$k$高的学生，相当于将学生总分从小到大排序后，下标为$l_A-k$的学生。代码如下：

public class Solution { // 将总分和其下标做成一个Pair类 class Pair { int idx, sum; public Pair(int idx, int sum) { this.idx = idx; this.sum = sum; } } /** * @param scores: two dimensional array * @param K: a integer * @return: return a integer */ public int FindTheRank(int[][] scores, int K) { // write your code here int len = scores.length; Pair[] pairs = new Pair[len]; for (int i = 0; i < len; i++) { int sum = 0; for (int score : scores[i]) { sum += score; } pairs[i] = new Pair(i, sum); } partition(pairs, 0, len - 1, len - K); return pairs[len - K].idx; } // 快速选择模板 private void partition(Pair[] pairs, int l, int r, int idx) { int m = l + (r - l >> 1); swap(pairs, l, m); Pair piv = pairs[l]; int i = l, j = r; while (i < j) { while (i < j && pairs[j].sum >= piv.sum) { j--; } pairs[i] = pairs[j]; while (i < j && pairs[i].sum <= piv.sum) { i++; } pairs[j] = pairs[i]; } pairs[i] = piv; if (i > idx) { partition(pairs, l, i - 1, idx); } else if (i < idx) { partition(pairs, i + 1, r, idx); } } private void swap(Pair[] pairs, int i, int j) { Pair tmp = pairs[i]; pairs[i] = pairs[j]; pairs[j] = tmp; } }

时间复杂度$O(n)$，空间$O(\log n)$，这里的复杂度都是平均复杂度。