算法——找出N个整数中最大的K个数（Java实现）_从n个数取第k大的数java

引言

  算法思路来自找出N个整数中最大的K个数，可以看出，TopK问题，基本上是排序算法的延伸：

1. 利用全排序，再倒数K个数；
2. 快速排序，分区分治；
3. 类似快速排序，分区找第K大的数；
4. 堆排序，建立最小堆；
5. 计数排序，先计数，再倒数K个数；

实现

import java.util.Arrays;
import java.util.Random;

public class TopK {

    private static int[] getRandomInts(int count, int max) {

        if (count <= 0 || max <= 0) {
            return null;
        }

        Random random = new Random();

        int[] result = new int[count];

        for (int i = 0; i < count; i++) {
            result[i] = random.nextInt(max);
        }

        return result;
    }


    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static int partition(int[] a, int left, int right) {
        int pivot = left;
        int index = pivot + 1;

        for (int i = index; i <= right; i++) {
            if (a[pivot] > a[i]) {
                swap(a, i, index);
                index++;
            }
        }

        swap(a, index - 1, pivot);

        return index - 1;
    }

    private static void partitionTopK(int[] a, int start, int end, int k) {

        if (k == 0) {
            return;
        }

        int left = start;
        int right = end;
        int partitionIndex = partition(a, left, right);

        if (right - partitionIndex + 1 < k) {
            partitionTopK(a, left, partitionIndex - 1, k - (right - partitionIndex + 1));
        } else if (right - partitionIndex + 1 > k) {
            partitionTopK(a, partitionIndex + 1, end, k);
        } else {
            return;
        }
    }

    private static int[] quickTopK(int[] a, int k) {
        int left, right;
        left = 0;
        right = a.length - 1;
        partitionTopK(a, left, right, k);

        return Arrays.copyOfRange(a, a.length - k, a.length);
    }

    private static void buildMinHeap(int[] a, int k) {
        for (int i = k / 2; i >= 0; i--) {
            heapAdjust(a, i, k);
        }
    }

    private static void heapAdjust(int[] a, int parentIndex, int length) {
        int leftIndex = parentIndex * 2 + 1;
        int rightIndex = parentIndex * 2 + 2;
        int smallest = parentIndex;

        if (leftIndex < length && a[leftIndex] < a[smallest]) {
            smallest = leftIndex;
        }

        if (rightIndex < length && a[rightIndex] < a[smallest]) {
            smallest = rightIndex;
        }

        if (smallest != parentIndex) {
            swap(a, smallest, parentIndex);
            heapAdjust(a, smallest, length);
        }
    }

    private static int[] heapTopK(int[] a, int k) {

        buildMinHeap(a, k);

        int length = a.length;
        int smallest = a[0];

        for (int i = k; i < length; i++) {
            if (a[i] > smallest) {
                swap(a, i, 0);
                heapAdjust(a, 0, k);
                smallest = a[0];
            }
        }

        return Arrays.copyOfRange(a, 0, k);
    }


    public static void main(String[] args) {

        int count, max, k;
        count = 20;
        max = 100;
        k = 5;

        int[] randomInts = getRandomInts(count, max);
        if (randomInts == null) {
            return;
        }

        int[] quickRandomInts = Arrays.copyOf(randomInts, randomInts.length);
        int[] quickTopK = quickTopK(quickRandomInts, k);
        System.out.println(Arrays.toString(quickTopK));

        int[] heapRandomInts = Arrays.copyOf(randomInts, randomInts.length);
        int[] heapTopK = heapTopK(heapRandomInts, k);
        System.out.println(Arrays.toString(heapTopK));


    }
}

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

一些思考

  排序算法作为非常重要的算法，不仅能够给出排序的各种实现，能够对比讨论算法时空间复杂度，而且是解决类似问题的基础，更重要的是，能够培养人用多个角度看待问题，逐步深入的解决问题。
  前两天看到一篇文章，其中提到，算法是创业成功的理论和实践基础。初步理解，这其中的“算法”是一种思路，但更是一种，“深入行业——认识问题——抽象问题——解决问题——从深度角度挖掘问题，螺旋上升”的自我进化，不确定有没有最好的，但是“我们一直在路上”。