博客

求一个数组中前K大的数（或者第K大的数），该数组不能使用排序算法，时间复杂度小于O(n^2)。

#include <iostream>
using namespace std;

void BubbleSort(int a[], int alen)
{
	for(int i = 0; i < alen; i++)
    	{
        	for(int j = alen-1; j > i; j--)
        	{
            		if(a[j] > a[j-1])
            		{
                		int t = a[j];
                		a[j] = a[j-1];
                		a[j-1] = t;
            		}
        	}
    	}
}

int findMax(int arr[], int arrlen, int K)
{
	if(arr == NULL || K <= 0 || K > arrlen)
		return -9999;

	int max[K+1]; //定义一个数组，保存最大到前Ｋ大的数，最后一位作为活动位
	for (int i = 0; i < K+1; ++i)
	{
		max[i] = -9999;　//赋给初值，可以为0，或者很小的数
	}

	for (int i = 0; i < arrlen; ++i)
	{
		if(arr[i] > max[K-1])
		{
			max[K] = arr[i]; //每次将原数组arr[]中的大于max[]数组中第K-1位的数的元素存入max[]的活动位
			BubbleSort(max, K+1); 
			/*将max[]进行冒泡排序，或者使用其他的排序算法，这里只是对max[]数组排序，没有对原数组arr[]排序。
			  每次取一个大于max[K-1]的元素存入max[]中的活动位max[K]中，然后进行排序，可以保持max[]数组一直
			  是前K大的元素*/
		}	
	}	
	return max[K-1]; //最后一位max[K]是活动位，返回第K-1位max[K-1]才是第K大的元素，前面存储了前K大的数
}


int main()
{
	int arr[] = {1,9,2,6,0,-5,4,-4,5,8,3,7};

	int arrlen = sizeof(arr) / sizeof(int);

	int res = findMax(arr, arrlen, n);

	cout <<"3: " << res << endl;
	
	return 0;
}

这个例子是输入第3大的数，可以更改位前K位数，这种方法的最坏时间复杂度为O(K^2 * n);

适用于Ｋ值不是很大的情况，即Ｋ^2 < n的情况。