度度熊想去商场买一顶帽子, 商场里有 N 顶帽子, 有些帽子的价格可能相同. 度度熊想买一顶价格第三便宜的帽子, 问第三便宜的帽子价格是多少?
思路堆排序, 手写堆较为复杂, 只需要用三个数代替就好了, 主要如果帽子价格相同要跳过循环.
- #include<iostream>
- #include<vector>
- #include<algorithm>
- using namespace std;
- int main() {
- int N;
- cin>> N;
- vector<int> v(N, 0);
- for (int i = 0; i<N; ++i) {
- cin>> v[i];
- }
- int
- min1 = 1000, min2 = 1000, min3 = 1000;
- for (int i = 0; i<N; ++i) {
- if
- (v[i]==min1||v[i]==min2||v[i]==min3)
- continue;
- if (v[i]<min3) {
- if (v[i]<min2) {
- if (v[i] <min1) {
- min3 = min2;
- min2 = min1;
- min1 = v[i];
- }
- else {
- min3 = min2;
- min2 = v[i];
- }
- }
- else min3 = v[i];
- }
- }
- if
- (min3 == 1000) cout << -1;
- else cout << min3;
- return 0;
- }
- ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
计数排序
类似哈希的思路, 空间复杂度较大, 用一个数组存价格, 就是简化吧的哈希, 从最小的价格开始找, 直到找到第三价格.
- #include<iostream>
- using namespace std;
- int main(){
- int n,t=0,syn=0;
- int price[
- 1000
- ]={
- 0
- };
- cin>>n;
- while(n--){
- cin>>t;
- price[t]=1;
- }
- t=0;
- for(int i=0;i<
- 1000
- ;i++){
- if(price[t]&&syn<
- 3
- )
- syn++;
- if(syn==
- 3
- )
- break;
- t++;
- }
- syn==
- 3
- ?cout<<t:cout<<-1;
- }
来源: http://www.bubuko.com/infodetail-2980760.html