bloomberg的
给一个int[] array, 找出其中出现次数为 even的数字，odd out. 一开始我用了排序，又给了
hashmap的方法，后来又给了条件说保证结果只有一个数字问有没有time O(n) no extra space 方
法。
看面经 这道题，想不出来 time O(n) no extra space的，因为是找 even 次数，所以 xor 也不试用
所以 求大家思路
谢谢！！
数字范围没有限制吗？
a^a = 0
a^0 = a
然后就可以了
哦哦 原来是找even
没有给范围的
如果 给的是 1 ---- n的话 就一个 even的 可以用binary search to find
额，还是错了，binary search 前提 是 array sorted的。。
但是没有范围 所以 我在想 怎么用 O(n) no extra space to find even appearance.
谢谢 x老师
是 找even appearance的
别的 都是 odd的 就算 iterate through the array 最后 还是 不会 找到 even appearance
可能是 我没明白您说的
您能再详细 说下么
谢谢！！
我这个好像只能找到odd。。 哎看错题目了 even怎么做呢 我持续关注一下
我的想法是可以参考 quicksort 里的选择 pivotal 做 partition 的机制，每次 on average 是discard half of the array，所以 runtime 总共是 O(n)
关键如何知道 even number 在哪个half
抱歉 可能 是我还没能理解明白
quicksort 的 worst case 是 O(n * n)
我们是想找 出现 次数 偶数次的 一个数字，如果 那个result 第一次的 话 就分别 在两边 请问 怎么discard
还是 您是想用 quick sort 把 他 sort 一下
抱歉 x 老师 读了您的 回复
我还是没能理解明白
quicksort 的 worst case 是 O(n * n)
我们是想找 出现 次数 偶数次的 一个数字，如果 那个result 第一次的 话 就分别 在两边 请问 怎么discard
还是 您是想用 quick sort 把 他 sort 一下