LeetCode

LeetCode-top-k-Kth-lagest

Top-k 问题有多种解法。LeetCode #215 #347

k次冒泡法

就是冒泡排序了，执行看次冒泡操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> kBubble(vector<int>& nums, int k){
	bool swapped;
	int n = nums.size();
	int topK = k;
    // 每次do{} 都是一次冒泡，即将最大值移到数组最右端
	do {
		if (topK==0) break;
		swapped= false;
		for (int i=1;i<n;i++){
			if (nums[i-1]>nums[i]){
				swap(nums[i-1], nums[i]);
				swapped = true;
			}
		}
		n--;
		topK--;
	}while(swapped);
    // 保存top k
	vector<int> res(nums.rbegin(), nums.rbegin()+k);
	return res;
}

测试:

1
2
3
4
5
6
7
8
9
10
int main(int argc, char** argv){

	vector<int> nums = {2,5,8,3,4,5,9,12,45,78,340,5,2};
	vector<int> res = kBubble(nums, 3);
	for (auto item:res)
		cout<<item<<" ";
	cout<<endl;

    return 0;
}

返回：

1
2
3
4
// 当k = 3
340 78 45 
// 当k = 数组大小
340 78 45 12 9 8 5 5 5 4 3 2 2

时间复杂度：O(N*K)

快排中的Partition操作法

先看，快排中的partition操作返回第k大的元素。其思路是，每次partition返回的值是一个索引值index，它对应的元素是在排好的序列中的正确位置。对于下面的例子，元素个数为9，k为2。一次partition操作后判断这个索引值index=4，对应元素5，5被放到它应该在的位置。而且9-4==5 != k，所以5不是第k个元素。

1
2
3
4
k=2
5 4 3 2 1 8 9 6 7 
// 一次partition操作后
4 3 2 1 [5] 8 9 6 7

则此时第2大的元素在以5为界的右半边，所以对右半边进行partition操作。假如返回index为7，而9-7==k，所以找到第2大元素8. 

1
4 3 2 1 [5] 6 7 [8] 9

上述是这个问题的关键。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// partition 操作
int partitionOpe(vector<int>& nums, int l, int r){
	swap(nums[l], nums[rand()%(r-l+1)+l]);
	int p = nums[l];
	int j = l;
	for (int i=j+1;i<=r;i++){
		if (nums[i]<p){
			swap(nums[i], nums[++j]);
		}
	}
	swap(nums[l], nums[j]);
	return j;
}

// 查找
int kthItem(vector<int>& nums, int k){
	int n = nums.size();
	int l=0, r=n-1, index=0;
	index = partitionOpe(nums,l,r);
	while(true){
		// 对右边进行partition
		if (n-index>k){
			l = index+1;
			index = partitionOpe(nums,l,r);
		}
		// 对左边进行partition
		else if(n-index<k){
			r = index-1;
			index = partitionOpe(nums,l,r);
		}
		// 直到找到
		else if(n-index==k){
			return nums[index];
		}
	}
}

测试对象[5,7,3,8,2,9,1,6,4], 返回第3大元素，结果：

1
2
3
4
// 结果
7
// 打印数组，7前元素比7小，7后元素比7大。
4 5 3 2 1 6 7 9 8

进而Top-k问题，就是将此时的数组返回7之后的所有元素（包括7）即可。

时间复杂度：

O(N(1+1/2+1/4+1/8+…)), 根据数列和的极限，1+1/2+1/4+1/8+… 趋近于2，所以partition操作的top-k问题时间复杂度为O(2N).

注意:

  1. 此法可以处理含有重复元素的数组。
  2. 不要忘了快排递归终止条件。

附件 快排

注意递归终止条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int partitionOpe(vector<int>& nums, int l, int r){
	swap(nums[l], nums[rand()%(r-l+1)+l]);
	int p = nums[l];
	int j = l;
	for (int i=j+1;i<=r;i++){
		if (nums[i]<p){
			swap(nums[i], nums[++j]);
		}
	}
	swap(nums[l], nums[j]);
	return j;
}
// 找到p值后分左右继续找。
void findPSplit(vector<int>& nums, int l, int r){
	// 递归终止条件！
	if (l>=r) return;  
	int p = partitionOpe(nums, l, r);
	findPSplit(nums, l, p-1);
	findPSplit(nums, p+1, r);
	return;
}
// 入口函数
void quickSort(vector<int>& nums){
	findPSplit(nums, 0, nums.size()-1);
	return;
}

优先队列法

找到第k的元素：

1
2
3
4
5
6
7
8
9
10
11
int findKthLargest(vector<int>& nums, int k) {
	// 1) 构造优先队列
	priority_queue<int> pq;
	for(auto itr=nums.begin(); itr!=nums.end(); itr++)
		pq.push(*itr);

	/// 求kth 元素
	for(int i=1;i<k;i++)
		pq.pop();
	return pq.top();
}

如果是求Top-k:

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> topKQueue(vector<int>& nums, int k){
	// 1) build a map:
	priority_queue<int> pq;
	for(auto item: nums)
		pq.push(item);

	vector<int> res;
	for(int i=0; i<k; i++){
		res.push_back(pq.top());
		pq.pop();
	}
	return res;
}

储存pop的结果得到top-k问题结果。

时间复杂度，与数据结构有关。