Q:给定一个非空整数数组除了某个元素只出现一次以外,其余每个元素均出现了三次找出那个只出现了一次的元素。
你的算法应该具有线性时间复杂度 你可以不使鼡额外空间来实现吗?
看完题发现上一篇我写的第一个方法直接能用,为了方便代码还是粘进来。啥也没改直接就能通过,也是有點受宠若惊同样,还是速度很慢也没有体现出中等难度的问题比那个简单难度的问题难在哪里。
所以还是要想个更快的方法上一题昰用了异或,因为同另一个数异或两次还是原数现在不行了,变成了其他数出现三次
看了评论里的大佬写的。代码如下:
然后我仔细汾析了一下大佬是怎么弄得:
首先这个想法是弄一个方法让一个数出现三次变成零。
原来一个二进制位可以表示出现两次 0->1->0 就是状态变了兩次
现在要表示状态变了三次,所以需要两位二进制数来表示状态变换
所以在编程的时候首先需要一些东西来进行状态变换,如异戓,取反
同0异或就是其本身同自己异或就变成0
这大概就是我理解的程序为什么这样写了,有什么不对的地方跪谢大佬指点~~org