算法 - 查找第K大数字

• 极客时间 - 数据结构与算法之美 - 12 | 排序（下）

本题目借助快排思想，算法描述：

• a为待 排序 数组，n为数组长度

1. 问题转换：把第k大数字转换成第l小数字，比如： n=5，k=1 ，那么 l=n-k+1=5 ，也就是第5小的数字，其下标 l_i=5-1=4 。
2. 取 a[n-1] 作为 pivot
3. 用快排的思路，把 < pivot 的元素放到 pivot 左边，把 >= pivot 的元素放到 pivot 右边，得到pivot的下标： pivot_i
4. 如果 pivot_i < l_i ，则说明被查找的数字可能在右边，对右边重复2-5步骤
5. 如果 pivot_i > l_i ，则说明被查找的数字可能在左边，对左边重复2-5步骤

代码：

public static int findKthBigNumber(int[] a, int kthBig) {
  int n = a.length;
  int lthSmall = n - kthBig;
  return quickFind(a, 0, a.length - 1, lthSmall);
}

private static int quickFind(int[] a, int start, int end, int lthSmall) {
  if (start > end) {
    return -1;
  }
  int pivot = a[end];

  int pivot_i = start;
  for (int j = start; j <= end - 1; j++) {
    if (a[j] < pivot) {
      int tmp = a[j];
      a[j] = a[pivot_i];
      a[pivot_i] = tmp;
      pivot_i++;
    }
  }

  a[end] = a[pivot_i];
  a[pivot_i] = pivot;

  if (pivot_i == lthSmall) {
    return a[pivot_i];
  }

  if (pivot_i < lthSmall) {
    return quickFind(a, pivot_i + 1, end, lthSmall);
  }

  return quickFind(a, start, pivot_i - 1, lthSmall);
}

算法复杂度分析：

最好情况：

k > n

最坏情况：

(n-1)+(n-2)+(n-3)+...+1=n(n-1)/2

平均情况：

• 不知怎么分析