topk問題求解

1）利用快排思路求解~

static int partation(vector<int>& v, int l, int r) {
	if (l > r) return -1;
	if (l == r) return l;
	int pivot = v[l];
	while (l < r) {
		while (l < r && v[r] >= pivot) r--;
		swap(v[l], v[r]);
		while (l < r && v[l] <= pivot) l++;
		swap(v[l], v[r]);
	}
	v[l] = pivot;
	return l;
}
static vector<int> getTopK(vector<int>& v, int k) {
	int n = v.size();
	vector<int> res;
	int l = 0, r = n - 1;
	int index = partation(v, l, r);
	while (index != k - 1) {
		if (index > k - 1) r = index - 1;
		else if (index < k - 1) l = index + 1;
		index = partation(v, l, r);
	}
	for (int i = 0; i < k; i++) {
		res.push_back(v[i]);
	}
	return res;
}
           

2）利用堆排序思想求解~

具體思路是根據topk問題類型來确定建立大頂堆和小頂堆，然後對剩餘的k+1~n的對比目前元素和堆頂元素大小進行判斷進而調整得到最後的元素。

static void heapAdjust(vector<int>& v, int index, int n) {
	int k = index, l = 2 * index + 1, r = 2 * index + 2;
	if (l < n && v[l] < v[k]) k = l;
	if (r < n && v[r] < v[k]) k = r;
	if (k != index) {
		swap(v[k], v[index]);
		heapAdjust(v, k, n);
	}
}
static void buildMinHeap(vector<int>& v, int n) {
	int i = n / 2 - 1;
	for (; i >= 0; i--) {
		heapAdjust(v, i, n);
	}
}
static void heapSort(vector<int>& v, int n) {
	buildMinHeap(v, n);
	for (int i = n - 1; i >= 0; i--) {
		swap(v[0], v[i]);
		heapAdjust(v, 0, i);
	}
}

static vector<int> getRes(vector<int>& v,int k) {
	int n = v.size();
	vector<int> tmp(k);
	for (int i = 0; i < k; i++) {
		tmp[i] = v[i];
	}
	buildMinHeap(tmp, k);
	for (int i = k; i < n; i++) {
		if (v[i] > tmp[0]) {
			tmp[0] = v[i];
			heapAdjust(tmp, 0, k);
		}
	}
	sort(tmp.begin(),tmp.end());
	return tmp;
}
           

3）利用優先隊列求解（底層實作其實還是大頂堆或者小頂堆）

struct cmp1 {
	bool operator()(int a,int b){
		return a > b;
	}
};
vector<int> getTopK(vector<int>& v, int k) {
	int n = v.size();
	priority_queue<int, vector<int>, cmp1> q;
	for (int i = 0; i < n; i++) {
		if (q.size() < k) {
			q.push(v[i]);
		}
		else {
			if (v[i] > q.top()) {
				q.pop();
				q.push(v[i]);
			}
		}
	}
	vector<int> res;
	while (!q.empty()) {
		int tmp = q.top();
		q.pop();
		res.push_back(tmp);
	}
	return res;
}