Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
给你一个数组,里边所有的数字都是有两个,只有两个数字是有一个的,找出这两个数字并且返回。
代码如下:
解题思路:把nums里所有的数字求异或(^),得到x_xor_y,然后求出mask,其中mask是这个数字,比如x_xor_y = 0110b , 那么mask = 0010b, 意思就是从右向左,找出第一个为1的位置。这个位置就是这两个数字在二进制中不同的地方,然后利用这个位置,将所有的数字分开异或,这个位置为1的异或,求出 x; 然后这个位置为0的异或,求出y。然后保存到vector。
求第一个为1的位置,利用公式: x & (~(x - 1))