leetcode260-- Single Number III

leetcode260-- Single Number III

题目

这个题目在剑指offer上面也有, 之前做过1.(只有一个元素出现一次,其它的都出现了两次), 2.(只有一个元素出现一次, 其它的都出现了三次), 3.(只有两个元素分只出现了一次,其它的都出现了两次.),那么这次就是第三道题,这个题的思路是想利用第一道题, 所以关键就是如何把这个大的数组分成两个小数组,然后这两个小的数组里面分别各自只有一个出现过一次的。具体的做法是先将所有的数字异或一下,这样最终得到的数肯定和那两个数异或得到的结果是一样的, 然后将结果按照某一位可以将所有的数分成两组,这样两组数中就会只有一个是只出现过一次的了.


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.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

    The order of the result is not important. So in the above example, [5, 3] is also correct.
    Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?


解答:


class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        xor = 0
        for i in nums:
            xor ^= i
        xor &= -xor # get the last 1 of xor: 10101000 -> 1000
        a, b = 0, 0
        for i in nums: # devide the numbers into two parts, and a, b should be divided into different part
            if i & xor:
                a ^= i
            else:
                b ^= i
        return [a, b]

这个的想法是想把数组分成两组,而且这两组中恰好都只有一个只出现一次的,

做法就是先将所有的数进行一个按位异或,得到的肯定是这两个只出现一次的数进行按位异或的结果,然后随便找到这个结果中的一个为1的位,按照这个位可以把数组分成两组,然后两组再分别全部按位异或一次,得到的就是最终的结果, 这里涉及到的有,如何得到为1的位,方法有很多,这里xor &= -xor 就是一种,在二进制里面负号就是补码的形式,而补码就是反码加1.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦