数组中其它元素都出现 k 次,只有一个元素出现一次,如何把它找出来。

好久没来更新博客了,最近也只是在修改了几次博客的模板。感觉再不更新就要杂草丛生了。

今天在刷微博的时候,无意间发现“秋大”转发了一个问题,感觉挺有意思的,但是自己的思路还是有些狭窄,还是通过他人的思路提醒才明白其中的奥妙的。

题目描述

一个数组中有一个元素只出现1次,其他所有元素都出现k次(k>1),求这个只出现1次的元素。要求:空间复杂度O(1),时间复杂度O(n).

前期的思路

首先我们将 k 分为奇数和偶数考虑。对于 k 为偶数来说,只要将每个数异或起来,那么剩下的就是最终结果了;但是对于 k 为奇数的情况,却没有很好的方法解决。于是这种方法先告一段落了。

比较完美的方法

这里我们不要将每个数作为整体,而是把它分为好几个二进制位来考虑。这样我们假设数组中的元素为 32 位的整型,然后对于每个数,将二进制位对应加起来的和 mod k 。那么结果就是 mod k 后的二进制位重新组合起来。

以后再补个代码理解一下吧。

后记 - To Be Continue

这种题目还有好多种变形,等以后整理一下,再整合到这篇博文里面吧。