算法 - 查找第K大数字

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

public static int findKthBigNumber(int[] a, int kthBig) {
  int n = a.length;
  if (kthBig > n) {
    return -1;
  }
  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_i = partition(a, start, end);

  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);

}

/**
 * 快排的分区算法
 *
 * @param a
 * @param start
 * @param end
 * @return 分区点
 */
private static int partition(int[] a, int start, int end) {
  int pivot = a[end];

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

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