---

TopK问题

输入数组arr，找出其中最大的k个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最大的4个数字是5、6、7、8。
示例一：
 输入：arr = [3,2,1], k = 2
 输出：[3,2]或者[2,3]
示例二：
 输入：arr = [0,1,2,1], k = 1
 输出：[2]

解决方法1：

先将这个数组排成降序，输出前K个数字即可！

注意
1.如果排升序，就建立大根堆
2.如果排降序，接建立小根堆

//交换函数
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//堆的向下调整（小堆）
void AdjustDown(int* a, int n, int parent)
{
	//child记录左右孩子中值较小的孩子的下标
	int child = 2 * parent + 1;//先默认其左孩子的值较小
	while (child < n)
	{
		if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小
		{
			child++;//较小的孩子改为右孩子
		}
		if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小
		{
			//将父结点与较小的子结点交换
			Swap(&a[child], &a[parent]);
			//继续向下进行调整
			parent = child;
			child = 2 * parent + 1;
		}
		else//已成堆
		{
			break;
		}
	}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
	*returnSize = k;
	int i = 0;
	//建小堆
	for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, arrSize, i);
	}
	//排降序
	int end = arrSize - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
	//将最大的k个数存入数组
	int* retArr = (int*)malloc(sizeof(int)*k);
	for (i = 0; i < k; i++)
	{
		retArr[i] = arr[i];
	}
	return retArr;//返回最大的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
56
57
58

时间复杂度: O(N+NlogN) 空间复杂度：O(N)

解决方法2：

将数组建成一个大堆，取K次堆顶的数据就可以了。细节：每次拿走堆顶的数据后，需要将堆顶的数据和最后一个数据进行交换，然后重新建堆！

//交换函数
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//堆的向下调整（大堆）
void AdjustDown(int* a, int n, int parent)
{
	//child记录左右孩子中值较大的孩子的下标
	int child = 2 * parent + 1;//先默认其左孩子的值较大
	while (child < n)
	{
		if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在并且右孩子比左孩子还大
		{
			child++;//较大的孩子改为右孩子
		}
		if (a[child] > a[parent])//左右孩子中较大孩子的值比父结点还大
		{
			//将父结点与较大的子结点交换
			Swap(&a[child], &a[parent]);
			//继续向下进行调整
			parent = child;
			child = 2 * parent + 1;
		}
		else//已成堆
		{
			break;
		}
	}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
	*returnSize = k;
	int i = 0;
	//建大堆
	for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, arrSize, i);
	}
	//将最大的k个数存入数组
	int* retArr = (int*)malloc(sizeof(int)*k);
	int end = arrSize - 1;
	for (i = 0; i < k; i++)
	{
		retArr[i] = arr[0];//取堆顶数据
		Swap(&arr[0], &arr[end]);//交换堆顶数据与最后一个数据
		//进行一次向下调整，不把最后一个数据看作待调整的数据，所以待调整数据为end=arrSize-1
		AdjustDown(arr, end, 0);
		end--;//最后一个数据的下标改变
	}
	return retArr;//返回最大的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

时间复杂度: O(N+klogN) 空间复杂度：O(N)

弊端：如果待待续的数字有100亿个，那么存储100亿个整数究竟需要多大的内存空间？让咱们来大概估算一下：
 我们知道1KB=1024byte，1MB=1024KB，1GB=1024MB，于是可以得出1GB大概有230个字节，也就是说1GB大概等于10亿个字节。
 存储100亿个整型需要400亿个字节，所以存储100亿个整型数据需要40G左右的内存空间。前面两种算法的空间复杂度均为O(N)，并不适合用于这种海量数据处理。

基于上述问题，我们重新建立一种新的解决方法！

解决方法3：

1.先将前K个数据建立小堆 2.将数组剩下的N-K个数字依次和堆顶的数据比较，如果大于堆顶的数据，进行替换，然后向下调整，使其仍为小堆。

//交换函数
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//堆的向下调整（小堆）
void AdjustDown(int* a, int n, int parent)
{
	//child记录左右孩子中值较小的孩子的下标
	int child = 2 * parent + 1;//先默认其左孩子的值较小
	while (child < n)
	{
		if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小
		{
			child++;//较小的孩子改为右孩子
		}
		if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小
		{
			//将父结点与较小的子结点交换
			Swap(&a[child], &a[parent]);
			//继续向下进行调整
			parent = child;
			child = 2 * parent + 1;
		}
		else//已成堆
		{
			break;
		}
	}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
	*returnSize = k;
	if (k == 0)
		return NULL;
	//用数组的前K个数建小堆
	int i = 0;
	int* retArr = (int*)malloc(sizeof(int)*k);
	for (i = 0; i < k; i++)
	{
		retArr[i] = arr[i];
	}
	for (i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(retArr, k, i);
	}
	//剩下的N-k个数依次与堆顶数据比较
	for (i = k; i < arrSize; i++)
	{
		if (arr[i]>retArr[0])
		{
			retArr[0] = arr[i];//堆顶数据替换
		}
		AdjustDown(retArr, k, 0);//进行一次向下调整
	}
	return retArr;//返回最大的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
56
57
58
59

时间复杂度: O(k+Nlogk) 空间复杂度：O(k)