蓝桥杯2013年第四届真题-错误票据 （C++代码）两种做法，hash和sort

解题思路:

       这个输入需要一些技巧，首先，他给的N表示输入多少行，然后每一行到底输入多少个数字我们不知道，这就需要我们去判断输入的结尾是不是换行号，这里提供了一个C++的判断方法：

while(cin>>a){
    if(cin.get()=='\n'){
        break;
    }
}
//输入一个a,如果监测到输入数据存在换行符'\n'则结束这个输入

这个技巧需要嵌套在while(n--)内已达到题目要求的效果，那么现在来介绍这两种做法。

1.sort方法，原理如下，建立一个数组，一股脑的将题目提供的数据全部存在这个数组中，然后将整体数组进行排序，再对已经排好序的数组进行遍历，找到数组中哪一段出现确实，哪一段出现重复，最后把这个数据输出就可以了，复杂度O(nlogn)//这取决于你的排序多有多快。

参考代码:

#include<bits/stdc++.h>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1000005;
int a[maxn]={0};
int n,pos=0;
int main(){
 hh;
 cin>>n;
 while(n--){
  while(cin>>a[pos]){
   pos++;
   if(cin.get()=='\n'){
    break;
   }
  }
 }
 int ansB=a[0],ansR=a[0];
 sort(a,a+pos);
 for(int i=0;i<pos;i++){
  if(a[i]!=a[i-1]+1&&a[i]!=a[i-1]){
   ansB=a[i]-1;
  }
  if(a[i]==a[i-1]){
   ansR=a[i];
  }
 }
 cout<<ansB<<' '<<ansR<<endl;
 return 0;
}

2.hash法，哈希法，建立一个初值全部为0的数组（哈希数组），然后每一个数据直接对应数组中的位置，使之+1，便利这一段数据，为0的就是缺失数据，为2的就是重复数据，同步于输入，我们在输入的时候把整体输入的最小值和最大值取出，这样我们可以减少便利的工作量，时间复杂度O(n)//比上面的快一点

#include<bits/stdc++.h>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=100005;
int hash_[maxn]= {0};
int n,temp;
int min_number=INT_MAX,max_number=INT_MIN;
int ansB,ansR; //B-->break,R-->Repeat
int main() {
 hh;
 cin>>n;
 while(n--) {
  while(cin>>temp) {
   if(min_number>temp) {
    min_number=temp;
   }
   if(max_number<temp) {
    max_number=temp;
   }
   hash_[temp]++;
   if(cin.get()=='\n') {
    break;
   }
  }
 }
 for(int i=min_number; i<=max_number; i++) {
  if(hash_[i]==0) {
   ansB=i;
  }
  if(hash_[i]==2) {
   ansR=i;
  }
 }
 cout<<ansB<<' '<<ansR<<endl;
 return 0;
}

刷题愉快~