大根堆、小根堆的应用—找中位数、O(logn)实现(你是不是只会排序呀,还不快点进来看看)

1、思路步骤:

 step:   1)先从用户获得一个数据,放在大根堆;
            2)在获得一个数据与大根堆的堆顶进行比较,若小于等于堆顶就放入大根堆,否则                    放入小根堆;
            3)再比较大根堆的size和小根堆的size,若两者相差超过2,就将size较大的那个的栈                     顶弹出放入size较小的堆中;
            4)循环往复,直到遍历完所有数字,若最后两堆的size不相等,就将size较大的那个                   堆顶 弹出个;否者都弹出取平均数。

2.代码实现: 

int findMedian(int arr[], int sz) {
	if (sz == 0)
		return arr[0];
	priority_queue<int,queue<int>,greater<int>> bigQ;//大根堆
	priority_queue<int,queue<int>,less<int>> smallQ;//小根堆
	bigQ.push(arr[0]);
	int bSz, sSz;
	for (int i = 1;i < sz;i++) {
		if (arr[i] <= bigQ.top()) //若小于等于堆顶就放入大根堆
			bigQ.push(arr[i]);
		else//否则放入小根堆
			smallQ.push(arr[i]);
		bSz = bigQ.size();//拿到大根堆的大小
		sSz = smallQ.size();//拿到小根堆的大小
		if (fabs(bSz - sSz) > 1) {
			if (bSz > sSz) {//就将size较大的那个的栈顶弹出放入size较小的堆中
				smallQ.push(bigQ.top());
				bigQ.pop();
			}
			else {
				bigQ.push(smallQ.top());
				smallQ.pop();
			}
		}
	}
	bSz = bigQ.size();
	sSz = smallQ.size();
	if (bSz > sSz)
		return bigQ.top();
	if (bSz < sSz)
		return smallQ.top();
	if (bSz = sSz)
		return (bigQ.top() + smallQ.top()) / 2;
}

上一篇:便捷打印封装


下一篇:【算法练习】校招研发工程师笔试题