位运算-数组中有两个数字只出现一次

75 阅读 0 评论 50 点赞

我是靠谱客的博主老迟到面包，最近开发中收集的这篇文章主要介绍位运算-数组中有两个数字只出现一次，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目来源：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

位运算，考虑异或操作。异或的特点：

1）任何数与本身的异或为0

2）任何数与0的异或为其本身

考虑一个整型数组nums，其中只有一个数字x只出现一次，其他数字均出现两次。那么将整个数组所有数字异或，由于除了x外，其他数字都出现了两次，异或结果为0，再与x异或，得到的异或结果就是x本身。

class Solution(object):
    def singleNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        x = 0
        for item in nums:
            x ^= item
        return x

回到本问题上，记两个只出现一次的数字分别为a，b。

如果对整个数组所有数字进行异或，那么得到的其实就是a与b的异或结果：a^b

再考虑到，a和b是不同的两个数字，那么异或后a^b一定不为0，至少有某一位的值为1。位值为1，说明a和b在该位的值不同。根据这一点，就可以将a和b划分到两个新的数组里。那么如何找到这一个位呢？从最低位开始，a^b的结果与1进行与，与的结果为0，说明a和b在该位上的值相同，则左移一位，重复这个判断过程。

找到a和b值不同的位后，其他数字也以这一位的值为依据进行划分。位值为0的分为第一组，位值为1的分为第二组。这样a和b被分在了两组里，再在数组里逐项异或就可以分别得到a和b。

class Solution(object):
    def singleNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 位运算
        r, a, b =0, 0, 0
        for item in nums:
            r ^= item   # 逐项异或，由于其他数字都出现了两次，因此最终结果就是两个一次数字的异或结果
        h = 1         # 假设最低位为1
        while r & h == 0:       # 和1与的结果为0，说明异或结果的相应位为0，说明两个数字该位的值相同，无法从该位区分这两个数字
            h <<= 1       # 位左移，再判断两个数字该位是否相同，直至找到不同的那一位
        for item in nums:
            if item & h == 0:      # 判断每个数字相应位为1还是0，位值相同的分为一组，从而将两个一次数字分到两组里
                a ^= item         
            else:
                b ^= item
        return [b, a]

参考：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/yi-huo-de-miao-yong-by-peterbrave/

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/zhi-chu-xian-yi-ci-de-shu-xi-lie-wei-yun-suan-by-a/