Top-K问题

P_M_P

发布于 2024-01-18 19:15:10

970

发布于 2024-01-18 19:15:10

文章被收录于专栏：算法 P_M_P学习笔记

问题：给定一个长度为 n的无序数组 nums ，请返回数组中前 k 大的元素。

💡方法一：遍历选择

我们可以进行k轮遍历，分别在每轮中提取第 1、2、…、k 大的元素，时间复杂度为 (nk) 。这种方法只适用于k<<n的时候，当k与n很接近时，时间复杂度趋近于O（n^2），效率不高。

💡方法二：排序

先对nums数组进行排序，然后提取最右边的k个元素，时间复杂度为O（nlogn）。很显然，这种方法在数据量较大时，耗时会比较长，属于是“超额”完成了。

💡方法三：堆

1.首先创建一个小根堆，堆顶元素最小 2.然后依次将数组的前k个数入堆 3.再从第k+1个数开始，依次与堆顶元素进行比较，如果大于堆顶元素，则堆顶元素出堆，此元素入堆（实现时，是直接将此元素的值赋值给堆顶元素） 4.遍历完成，得到最大的k个元素 时间复杂度O（N*logk）

typedef  int HPDataType;
void swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int child)
{
	//数组中父节点的下标比子节点的下标小
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])//小堆（大堆时是>）
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
			//parent=(parent-1)/2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(int* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child+1<size&&a[child + 1] < a[child])//找兄弟节点中较小的那一个，再交换  //小堆（大堆时是>）
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
			//child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
int findKthLargest(int* nums, int numsSize, int k){
	int* minheap=(int*)malloc(sizeof(int)*k);
	memset(minheap,0,k*sizeof(int));
	for(int i=0;i<k;i++)
	{
		minheap[i]=nums[i];
		AdjustUp(minheap,i);
	}
	for(int i=k;i<numsSize;i++)
	{
		if(nums[i]>minheap[0])
		{
			minheap[0]=nums[i];
			AdjustDown(minheap,k,0);
		}
		
	}
	return minheap[0];
}

如果想要时最后得到的k个元素有序，还可以像下面这样，每次将堆顶元素与最后一个元素进行交换，再把堆看作删除了最后一个元素（实际上并没有），然后再对堆进行向下调整：

//得到一个降序序列
int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

提示：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

typedef  int HPDataType;
void swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int child)
{
	//数组中父节点的下标比子节点的下标小
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])//小堆（大堆时是>）
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
			//parent=(parent-1)/2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(int* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child+1<size&&a[child + 1] < a[child])//找兄弟节点中较小的那一个，再交换  //小堆（大堆时是>）
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
			//child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
int findKthLargest(int* nums, int numsSize, int k){
	int* minheap=(int*)malloc(sizeof(int)*k);
	memset(minheap,0,k*sizeof(int));
	for(int i=0;i<k;i++)
	{
		minheap[i]=nums[i];
		AdjustUp(minheap,i);
	}
	for(int i=k;i<numsSize;i++)
	{
		if(nums[i]>minheap[0])
		{
			minheap[0]=nums[i];
			AdjustDown(minheap,k,0);
		}
		
	}
	return minheap[0];
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-12-27，如有侵权请联系 cloudcommunity@tencent.com 删除

排序