首页 > 代码库 > 百度2017笔试题:寻找n个员工中未打卡的那一个

百度2017笔试题:寻找n个员工中未打卡的那一个

声明:图片来自网络,笔者只是试着做了一下,然后做个记录。

技术分享

拿到这个题目的时候,笔者首先想到的是二分。两个数组,一个是全体员工的集合A;一个是缺少一人的集合B。对A,B排序,再对B进行二分,得到B的中间员工的工号mid,若A[mid] == B[mid],那么缺席员工的工号在mid之后,继续二分;若A[mid] < B[mid],那么缺席员工的工号在mid之前,继续二分。值得注意的是,这里A[mid]是不会大于B[mid]的。另外,这里的二分仅针对缺席工号在数组中间的情况。若缺席工号在数组(当然是排序后)首尾,单独处理即可。

 1 #include <bits/stdc++.h> 2 using namespace std; 3  4 typedef long long LL; 5 #define MOD        1000000007ll 6 #define PI         acos(-1.0) 7 const double EPS = 1e-6; 8 //const double PI  = acos(-1.0); 9 const int INF = 0x3f3f3f3f;10 //const LL  MOD = 1e9+7;11 12 template <class T> inline T bigMod(T p, T e, T M){13     long long ret = 1;14     for(; e > 0; e >>= 1){15         if(e & 1) ret = (ret * p) % M;16         p = (p * p) % M;17     } return (T)ret % M;    // Attention: bigMod(p, 0, 1), so ret has to module M.18 }19 template <class T> inline T modInverse(T a, T M){return bigMod(a, M-2, M);}20 template <class T> inline T gcd(T a, T b){return b ? gcd(b, a%b) : a;}21 int main() {22     int T;23     scanf("%d", &T);24     for (int i = 1; i <= T; ++i) {25         vector<int> total;26         vector<int> arrive;27         int num; cin >> num;28         for (int j = 0; j < num; ++j) {29             int employee; cin >> employee;30             total.push_back(employee);31         }32         for (int j = 0; j < num - 1; ++j) {33             int arriver; cin >> arriver;34             arrive.push_back(arriver);35         }36         /***     binary search37         sort(total.begin(), total.end());38         sort(arrive.begin(), arrive.end());39         if (total[0] != arrive[0]) cout << total[0] << endl;40         else if (total[num-1] != arrive[num-2]) cout << total[num-1] << endl;41         else {42             int left = 0, right = num - 2;43             while(left <= right) {44                 int mid = left + (right - left)/2;45                 if (total[mid] == arrive[mid]) {46                     left = mid + 1;47                 }else if (total[mid] < arrive[mid]){48                     right = mid - 1;49                 }50             }51             cout << total[left] << endl;52         }*/53         int num1 = 0;54         for (auto iter = total.begin(); iter != total.end(); ++iter) {55             num1 = num1 ^ *iter;56         }57         int num2 = 0;58         for (auto iter = arrive.begin(); iter != arrive.end(); ++iter) {59             num2 = num2 ^ *iter;60         }61         cout << (num1 ^ num2) << endl;62     }63     return 0;64 }

后来有个朋友提出了一个更好的方法,简直漂亮。利用异或的思想。

我们先来看这样一个表达式: p ^ q = m, m等于p,q的异或。那么有,p = q ^ m,  q = p ^ m。

现在,回过头来看这个题目。我们把A中的元素互相异或得到m;把B中的元素互相异或得到p。那么,没来的哪个员工工号是q=m^p。

代码的实现也综合在上诉代码中。

百度2017笔试题:寻找n个员工中未打卡的那一个