【Everyday】(16)落单的数到位运算 - Everyday - SegmentFault
给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
样例
给出 [1,2,2,1,3,4,3]，返回 4
挑战
一次遍历，常数级的额外空间复杂度
解题思路
找到落单数字，一个很笨的方法，开一个很大的数组，然后遍历之后，记录下来，然后再遍历一遍，进一步提升的方法是借助于位运算，其它的数均出现两次，想到位运算中，两个相同的数字通过异或运算之后为零，所以将其遍历一次进行异或运算，最后得出的数字即为我们所要求的落单数字。
Read full article from 【Everyday】(16)落单的数到位运算 - Everyday - SegmentFault
No comments:
Post a Comment