度度熊想去商場買一頂帽子，商場里有N頂帽子，有些帽子的價格可能相同。度度熊想買一頂價格第三便宜的帽子，問第三便宜的帽子價格是多少？
輸入描述:

首先輸入一個正整數(shù)N（N <= 50），接下來輸入N個數(shù)表示每頂帽子的價格（價格均是正整數(shù)，且小于等于1000）

輸出描述:

如果存在第三便宜的帽子，請輸出這個價格是多少，否則輸出-1

示例1

輸入

10

10 10 10 10 20 20 30 30 40 40

輸出

30

思路：排序之后去重。
方法一：直接調(diào)用STL去重。

#include<iostream> #include<algorithm> using namespace std; int main(){ int n,tmp; cin>>n; vector<int> v; while(n--){ cin>>tmp; v.push_back(tmp); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); cout<<(v.size()<3?-1:v[2]); return 0; }

方法二：雙指針法去重。

#include<iostream> #include<algorithm> using namespace std; int main(){int n,tmp;cin>>n;vector<int> v;while(n--){cin>>tmp;v.push_back(tmp);}sort(v.begin(),v.end());int index=0;for(int i=1;i<v.size();i++){if(v[index]!=v[i])v[++index]=v[i];}cout<<(index+1<3?-1:v[2]);return 0; }

發(fā)散一：假設(shè)允許一個重復(fù)的情況。

class Solution { public:int removeDuplicates(vector<int>& nums) {if(nums.size()<=2) return nums.size();int index=2;for(int i=2;i<nums.size();i++){if(nums[index-2]!=nums[i])nums[index++]=nums[i];}return index;} };

發(fā)散二：假設(shè)允許k個重復(fù)的情況。
可以用一個變量count來記錄允許重復(fù)的次數(shù)，下面是leetcode相關(guān)問題的通解。

class Solution { public:int removeDuplicates(vector<int>& A，k) {int n=A.size();if (n <= k) return n;int i = 1, j = 1;int cnt = 1;while (j < n) {if (A[j] != A[j-1]) {cnt = 1;A[i++] = A[j];}else {if (cnt < k) {A[i++] = A[j];cnt++;}}++j;}return i;} };

總結(jié)

以上是生活随笔為你收集整理的百度2017春招笔试真题编程题集合--买帽子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。