狗家店面

给一个array，所有的element都是相邻且pair up的除了一其中一个，要求找出这一个single element
比如221199522，返回5
先给了一个linear scan的解法，要求提高时间复杂度，于是给了binary search的做法，大概就

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

corner case 需要注意，比如一个element的情况， 112的情况。最后还问了如何测试和code coverage。大米大米老铁们

single element in a sorted array, 蠡口原题

XOR bit操作即可~~

补充内容 (2019-1-31 23:53):
log n的解法楼住时正确的~~

如果没排序，异或求多余元素，时间O(N)，但此题相同元素是相邻的，感觉楼主说得O(logN)二分解应该是面试官想要的

补充一下，linear scan 也有一些corner case 需要注意，比如一个element的情况， 112的情况。最后还问了如何测试和code coverage。大米大米老铁们

bdhmwzfa 发表于 2019/01/31 15:20:59
single element in a sorted array, 蠡口原题

其实不一定需要sorted也可以二分搜索

叼阿，桥头莽夫

return std::accumulate(nums.begin(), nums.end(), 0, std::bit_xor<int>());

shidaohang 发表于 2019/02/02 08:28:36
return std::accumulate(nums.begin(), nums.end(), 0, std::bit_xor<int>());

对对 binary search 是对的