百度2017春招笔试真题编程题集合--买帽子

度度熊想去商场买一顶帽子，商场里有N顶帽子，有些帽子的价格可能相同。度度熊想买一顶价格第三便宜的帽子，问第三便宜的帽子价格是多少？
输入描述:

首先输入一个正整数N（N <= 50），接下来输入N个数表示每顶帽子的价格（价格均是正整数，且小于等于1000）

输出描述:

如果存在第三便宜的帽子，请输出这个价格是多少，否则输出-1

示例1

输入

10

10 10 10 10 20 20 30 30 40 40

输出

30

思路：排序之后去重。
方法一：直接调用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; }

发散一：假设允许一个重复的情况。

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;} };

发散二：假设允许k个重复的情况。
可以用一个变量count来记录允许重复的次数，下面是leetcode相关问题的通解。

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;} };

总结

以上是生活随笔为你收集整理的百度2017春招笔试真题编程题集合--买帽子的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。