Skip to content

Commit 314286f

Browse files
gaohanghanggaohanghang
committed
<新增>(面试题): 获取数组中的前K个最大元素解法
1 parent 1fcf9fe commit 314286f

6 files changed

Lines changed: 581 additions & 14 deletions

File tree

‎src/a0算法面试题/_2019_1_21面试题/topk/FindTopK2.java‎

Lines changed: 66 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,83 @@
11
package a0算法面试题._2019_1_21面试题.topk;
22

33
import java.util.ArrayList;
4+
import java.util.Arrays;
45
import java.util.List;
6+
import java.util.logging.Logger;
7+
import java.util.stream.Collectors;
58

69
/**
710
* @Description:
811
* @author: Gao Hang Hang
912
* @date 2019/01/23 16:14
1013
*/
1114
public class FindTopK2 {
12-
public static List<Integer> findTopK(int[] a, int k) {
13-
int min = a[0];
14-
int max = a[0];
15-
for (int i = 0; i < a.length; i++) {
16-
if (max < a[i]) {
17-
max = a[i];
18-
}
19-
if (max > a[i]) {
20-
min = a[i];
15+
16+
/*
17+
虽然我们不会采用快速排序的算法来实现TOP-K问题，但我们可以利用快速排序的思想，在数组中随机找一个元素key，将数组分成两部分Sa和Sb，其中Sa的元素>=key，Sb的元素<key，然后分析两种情况：
18+
19+
* 若Sa中元素的个数大于或等于k，则在Sa中查找最大的k个数
20+
* 若Sa中元素的个数小于k，其个数为len，则在Sb中查找k-len个数字
21+
22+
如此递归下去，不断把问题分解为更小的问题，直到求出结果。
23+
24+
该算法的平均时间复杂度为O(N * logk)。以求K大的数为例，算法实现如下：
25+
*/
26+
27+
public static int findTopK(int[] a, int lo, int hi, int k) {
28+
int index = -1;
29+
if (lo < hi) { // 如果lo < hi直接返回-1
30+
int j = partition(a, lo, hi);
31+
int len = j - lo + 1; // 12345 01234
32+
if (len == k) {
33+
index = j;
34+
} else if (len < k) { // Sa中元素个数小于K, 到
35+
index = findTopK(a,j + 1, hi, k);
36+
} else { // Sa中元素的个数大于或等于k
37+
index = findTopK(a, lo, hi -1, k);
2138
}
2239
}
23-
List<Integer> topKList = new ArrayList<>();
24-
return null;
40+
return index;
2541
}
2642

43+
/**
44+
* 按切分元素划分数组，左边的元素大于切分元素，右边的元素小于切分元素
45+
*/
46+
public static int partition(int[] a, int lo, int hi) {
47+
// 将数组切分为a[lo..i-1], a[i], a[i+1..hi]
48+
int i = lo, j = hi + 1; // 左右扫描指针
49+
int v = a[lo]; // 切分元素
50+
while (true) {
51+
// 扫描左右，检查是否结束并交换元素
52+
while (less(v, a[++i])) if (i == hi) break; // 从左边找到比v 大元素
53+
while (less(a[--j], v)) if (j == lo) break; // 从右边找到比v 小的元素
54+
if (i > j) break;
55+
exch(a, i, j);
56+
}
57+
exch(a, lo, j); // 将v = a[j]放入正确的位置
58+
return j;
59+
}
2760

61+
private static boolean less(int v, int w) {
62+
return v < w;
63+
}
64+
65+
private static void exch(int[] a, int i, int j) {
66+
int t = a[i];
67+
a[i] = a[j];
68+
a[j] = t;
69+
}
70+
71+
private static void show(int[] a) {
72+
// 在单行打印数组
73+
for (int i = 0; i < a.length; i++)
74+
System.out.println(a[i] + " ");
75+
}
76+
77+
public static void main(String[] args) {
78+
int k = 4;
79+
int[] a = {20, 100, 4, 2, 87, 9, 8, 5, 46, 26};
80+
findTopK(a, 0, a.length - 1, k);
81+
System.out.println("array top k:{" + Arrays.stream(a).mapToObj(value -> String.valueOf(value)).limit(k).collect(Collectors.joining(",")) + "}");
82+
}
2883
}

‎src/a0算法面试题/_2019_1_21面试题/topk/FindTopK3.java‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
package a0算法面试题._2019_1_21面试题.topk;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
import java.util.stream.Collectors;
7+
8+
/**
9+
* @Description:
10+
* @author: Gao Hang Hang
11+
* @date 2019/01/26 18:10
12+
*/
13+
public class FindTopK3 {
14+
15+
/*
16+
解法三
17+
寻找Ｎ个数中的第Ｋ大的数，可以将问题转化寻找Ｎ个数中第K大的问题。对于一个给定的数p， 可以在O(N)的时间复杂度内找出所有不小于P的数。
18+
19+
根据分析，可以使用二分查找的算法思想来寻找Ｎ个数中第K大的数。假设N个数中最大的数为Vmax，最小的数为Vmin, 那么Ｎ个数中第K大的数一定在区间[Vmin,Vmax]之间。然后在这个区间使用二分查找算法。算法实现如下：
20+
21+
总结：该算法实际应用效果不佳，尤其是不同的数据类型需要确定max - min > delta，因此时间复杂度跟数据分布有关。 整个算法的时间复杂度为O(N * log（Vmax-Vmin）/delta)，在数据分布平均的情况下，时间复杂度为O(N * logN)。
22+
*/
23+
public static List<Integer> findTopK(int[] a, int k) {
24+
int max = a[0];
25+
int min = a[0];
26+
for (int i = 0; i < a.length; i++) {
27+
if (max < a[i]) {
28+
max = a[i];
29+
}
30+
if (min > a[i]) {
31+
min = a[i];
32+
}
33+
}
34+
List<Integer> topKList = new ArrayList<>();
35+
int key = findK(a, max, min, k); // 找到第k大元素
36+
for (int i = 0; i < a.length; i++) {
37+
if (a[i] >= key) {
38+
topKList.add(a[i]);
39+
}
40+
}
41+
return topKList;
42+
}
43+
44+
/**
45+
* 寻找第K大的元素
46+
*
47+
* @param array
48+
* @param max
49+
* @param min
50+
* @param k
51+
* @return
52+
*/
53+
private static int findK(int[] array, int max, int min, int k) {
54+
while (max - min > 1) {
55+
int mid = (max + min) / 2;
56+
int num = findKNum(array, mid);
57+
if (num >= k) {
58+
min = mid;
59+
} else {
60+
max = mid;
61+
}
62+
}
63+
return min;
64+
}
65+
66+
/**
67+
* 统计不小于key的元素个数
68+
*
69+
* @param array
70+
* @param key
71+
* @return
72+
*/
73+
private static int findKNum(int[] array, int key) {
74+
int sum = 0;
75+
for (int i = 0; i < array.length; i++) {
76+
if (array[i] >= key) sum++;
77+
}
78+
return sum;
79+
}
80+
81+
public static void main(String[] args) {
82+
int k = 4;
83+
int[] a = {20, 100, 4, 2, 87, 9, 8, 5, 46, 26};
84+
List<Integer> topK = findTopK(a, k);
85+
System.out.println(topK);
86+
}
87+
}

‎src/a0算法面试题/_2019_1_21面试题/topk/FindTopK4.java‎

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
package a0算法面试题._2019_1_21面试题.topk;
2+
3+
import javafx.geometry.VPos;
4+
5+
import java.util.Arrays;
6+
import java.util.List;
7+
8+
/**
9+
* @Description:
10+
* @author: Gao Hang Hang
11+
* @date 2019/01/26 18:33
12+
*/
13+
public class FindTopK4 {
14+
/*
15+
最大K最小堆
16+
最小K最大堆
17+
18+
上面几种解法都会对数据访问多次，那么就有一个问题，当数组中元素个数非常大时，如：100亿，这时候数据不能全部加载到内存，就要求我们尽可能少的遍历所有数据。针对这种情况，下面我们介绍一种针对海量数据的解决方案。
19+
20+
在学习堆排序的过程中，我们知道了堆这种数据结构。为了查找Top k大的数，我们可以使用小根堆来存储最大的K个元素。小根堆的堆顶元素就是最大K个数中最小的一个。每次考虑下一个数x时，如果x比堆顶元素小，则不需要改变原来的堆。如果想x比堆顶元素大，那么用x替换堆顶元素， 同时，在替换之后，x可能破坏最小堆的结构，需要调整堆来维持堆的性质。算法实现如下：
21+
22+
总结：该算法只需要扫描所有的数据一次，且不会占用太多内存空间（只需要容纳K个元素的空间），尤其适合处理海量数据的场景。算法的时间复杂度为O(N * logk)，这实际上相当于执行了部分堆排序。
23+
扩展：当K仍然很大，导致内存无法容纳K个元素时，我们可以考虑先找最大的K1个元素，然后再找看K1+1到2*K1个元素，如此类推。（其中容量为K1的堆可以完全载入内存）
24+
*/
25+
public static int[] findTopK(int[] array, int k) {
26+
int heapArray[] = new int[k];
27+
for (int i = 0; i < k; i++) {
28+
heapArray[i] = array[i];
29+
}
30+
buildMaxHeap(heapArray);
31+
for (int i = k; i < array.length; i++) {
32+
if (array[i] > heapArray[0]) {
33+
heapArray[0] = array[i];//更新堆顶
34+
adjustMaxHeap(heapArray, 0, heapArray.length);
35+
}
36+
}
37+
return heapArray;
38+
}
39+
40+
/**
41+
* 构建小根堆
42+
*
43+
* @param array
44+
*/
45+
public static void buildMaxHeap(int[] array) {
46+
for (int i = array.length / 2 - 1; i >= 0; i--) {
47+
adjustMaxHeap(array, i, array.length);
48+
}
49+
}
50+
51+
/**
52+
* 调整堆结构
53+
*
54+
* @param array
55+
* @param root 根节点
56+
* @param length
57+
*/
58+
public static void adjustMaxHeap(int[] array, int root, int length) {
59+
int left = root * 2 + 1; //左节点下标，数组下标从0开始，所以加1
60+
int right = left + 1; //右节点下标
61+
int largest = root;// 存放三个节点中最大节点的下标
62+
if (left < length && array[left] < array[root]) { //左节点小于根节点，更新最大节点的下标
63+
largest = left;
64+
}
65+
if (right < length && array[right] < array[largest]) {//右节点小于根节点，最大节点的下标
66+
largest = right;
67+
}
68+
if (root != largest) {
69+
swap(array, largest, root);
70+
adjustMaxHeap(array, largest, length);
71+
}
72+
}
73+
74+
/**
75+
* 交换
76+
*
77+
* @param a
78+
* @param i
79+
* @param j
80+
*/
81+
public static void swap(int[] a, int i, int j) {
82+
int t = a[i];
83+
a[i] = a[j];
84+
a[j] = t;
85+
}
86+
87+
public static void main(String[] args) {
88+
int k = 4;
89+
int[] a = {20, 100, 4, 2, 87, 9, 8, 5, 46, 26};
90+
int[] topK = findTopK(a, k);
91+
System.out.println(Arrays.toString(topK));
92+
}
93+
}

‎src/a0算法面试题/_2019_1_21面试题/topk/FindTopK5.java‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package a0算法面试题._2019_1_21面试题.topk;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
/**
8+
* @Description:
9+
* @author: Gao Hang Hang
10+
* @date 2019/01/26 19:18
11+
*/
12+
public class FindTopK5 {
13+
/*
14+
TOP-K问题是一个经典的问题，这个问题是存在线性算法的，只不过算法的使用范围有一定的限制。
15+
如果所有N个数都是正整数，且他们的取值范围并不大，可以考虑申请空间，记录每个整数出现的次数，然后再从大到小取最大的K个。
16+
实际就是利用计数排序的思想。 假设所有整数都在（0，maxN）区间，利用一个数组count[maxN]来记录每个整数出现的次数。count[i]表示整数i在N个数中出现的次数。只需要扫描一遍就可以得到count数组，然后寻找第K大的元素。算法实现如下：
17+
18+
这是一个典型的以空间换取时间的做法。当数组中取值范围比较大时，是及其浪费空间的。如[3,1...9999]，为了求出最大的K个元素，需要额外申请一个长度为10000的数组。
19+
20+
极端情况下，如果 N 个整数各不相同，我们甚至只需要一个 bit (0,1) 来存储这个整数是否存在，这样可节省很大的内存空间。
21+
*/
22+
23+
public static List<Integer> findTopK(int[] array, int k) {
24+
int max = array[0];
25+
for (int i = 0; i < array.length; i++) {
26+
if (max < array[i]) {
27+
max = array[i];
28+
}
29+
}
30+
int count[] = new int[max + 1];
31+
for (int i = 0; i < array.length; i++) {
32+
count[array[i]] += 1;
33+
}
34+
List<Integer> topKList = new ArrayList<>();
35+
for (int sumCount = 0,j = count.length - 1; j >= 0; j--) {
36+
int c = count[j];
37+
sumCount += c;
38+
if (c > 0) {
39+
for (int i = 0; i < c; i++) { // 如果c = 2 比如100有两个说明，要add两次
40+
topKList.add(j);
41+
}
42+
}
43+
if (sumCount >= k) {
44+
break;
45+
}
46+
}
47+
return topKList;
48+
}
49+
50+
public static void main(String[] args) {
51+
int k = 4;
52+
int[] a = {20, 100, 4, 2, 87, 9, 8, 5, 46, 26};
53+
List<Integer> topK = findTopK(a, k);
54+
System.out.println(topK);
55+
}
56+
}

0 commit comments

Comments
 (0)