数组中第k大的数字

发表于   |   分类于   |  

问题描述

从给定长度的整数数组中，选取第K大的数字。要求时间复杂度为O(N).

解决方法

1）需要查找的数组a，选取其中一个数字ai作为Key
2) 小于Key的数字放在Key左侧
3）大于等于Key的数字放在Key右侧
4）如果Key的下标keyIndex等于K，返回Key；
5）如果keyIndex 小于K，end = keyIndex - 1，重复1）
6）如果keyIndex 大于K，start = keyIndex + 1，重复1）

　　这种求解方法是快速排序的思路演化而来。
　　个人想到的一个将元素依据大小放置在Key左右的方法。
　　使用两个辅助数组，一个保存大于Key的元素，一个保存小于Key的元素。将小于Key的元素放置在头部，将小于Key的元素放于尾部。将剩余的空间放置Key。
　　优点：可以得到于Key相同的所有元素，对于相同元素多的数组可以加快速度
　　缺点：耗时，需要辅助空间

衍生问题

  • 给定整数数组中，求前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

package acm;

import java.util.Scanner;

/**
 * Created by hubaobin on 16/7/24.
 */
public class Kth {
    /**
     * @param start 开始的下标
     * @param end 结束的下标
     */
    public static int getKth(int[] a, int k, int start, int end) {
        int first = start;
        int last = end;
        //选取第一个数字作为key,建议还是随机选取避免选取数字过小或者过大
        int key = a[first];
        //将小于key的值放在key左侧,大于等于key的值放在右侧
        while (first < last) {
            //一定要先从后到前扫描
            while (first < last && a[last] >= key) last--;
            a[first] = a[last];
            while (first < last && a[first] <= key) first++;
            a[last] = a[first];
        }
        a[first] = key;
        if (first == k) return a[first];
        if (first > k) return getKth(a, k, start, first - 1);
        return getKth(a, k, first + 1, end);
    }

    public static void main(String[] args) {
        int[] a = {2, 7, 3, 8, 4, 9, 6, 1, 10, 5};
        Scanner scanner = new Scanner(System.in);
        int k;
        while ((k = scanner.nextInt()) != -1) {
            System.out.println(getKth(a, k - 1, 0, 9));
        }

    }
}