+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-03(70)

2020-04(60)

2020-05(24)

2020-06(39)

2020-07(23)

位运算-040-数组中只出现一次的数字

发布于2019-12-07 16:41     阅读(386)     评论(0)     点赞(26)     收藏(3)


0

1

2

3

4

5

6

7


原题:260. 只出现一次的数字 III (leetcode)

题目描述

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 : 输入: [1,2,1,3,2,5] 输出: [3,5]

注意:
结果输出的顺序并不重要,对于上面的例子, [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

分析

我们可以利用双层循环以O(n2n^2)的时间复杂度,O(1)的空间复杂度来解决,但是不符合要求;当然我们也可以利用Hash字典数据结构在O(n)的时间复杂度,O(n)的空间复杂度来解决,但是依然不符合要求;

于是我们根据163题中异或的思想来解决:

  1. 全部元素异或消掉出现两次的数字. 异或的结果为s.
  2. 寻找slowbit值. lowbit(s)s二进制表达式中最右边的1所对应的值. 因此lowbit(s)二进制表达式中只有一个bit 1.
    lowbit(s) = s & -s
    例如: s=1010
    lowbit(s) = 1010 & 0110 = 0010 = 2
  3. lowbit(s)将数组分成两组. 一组中,元素A[i] & lowbit(s) == lowbit(s), 即包含lowbit(s)的bit 1. 剩余的是另一组.
    而且,两个不同数也一定分在不同组. 因为异或值s中的bit1就是因为两个数字的不同而贡献的.
  4. 同一组的元素再异或求出不同数字. 出现两次的数字, 肯定出现同一组, 异或后消除掉.也就是说结果二进制只存在一个1,就是n最低位的1.

代码

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        s = 0
        for i in nums:
            s ^= i
        
        mask = s&(-s)

        res1 = 0
        res2 = 0
        for i in nums:
            if i&mask == mask:
                res1 ^= i
            else:
                res2 ^= i
        
        return res1,res2

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

0

1

2

3

4

5

6

7

8



所属网站分类: 技术文章 > 博客

作者:9384vfnv

链接: https://www.pythonheidong.com/blog/article/170112/157eb602290145339bd5/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

26 0
收藏该文
已收藏

评论内容:(最多支持255个字符)