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]

境界一

代碼如下：

//交換函式
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個數
}

時間復雜度： O ( N + N l o g N ) O(N+NlogN) O(N+NlogN)?空間復雜度： O ( N ) O(N) O(N)

境界二

?要知道進行一次向下調整的時間復雜度為 O ( l o g N ) O(logN) O(logN)，而進行一次建堆的時間復雜度為 O ( N ) O(N) O(N)，

代碼如下：

//交換函式
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個數
}

時間復雜度： O ( N + k l o g N ) O(N+klogN) O(N+klogN)?空間復雜度： O ( N ) O(N) O(N)

境界三

?存盤100億個整數究竟需要多大的記憶體空間？讓咱們來大概估算一下：
?我們知道1KB=1024byte，1MB=1024KB，1GB=1024MB，于是可以得出1GB大概有2³⁰個位元組，也就是說1GB大概等于10億個位元組，
?存盤100億個整型需要400億個位元組，所以存盤100億個整型資料需要40G左右的記憶體空間，前面兩種演算法的空間復雜度均為O(N)，并不適合用于這種海量資料處理，

代碼如下：

//交換函式
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個數
}

時間復雜度： O ( k + N l o g k ) O(k+Nlogk) O(k+Nlogk)?空間復雜度： O ( k ) O(k) O(k)