算法现学现卖—— 有趣的位运算(一)

作者:杨润炜
日期:2020/5/14 08:50

有趣的位运算 —— 异或排除重复的元素

  • leetcode 136. 只出现一次的数字

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

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

    示例 2:
    输入: [4,1,2,1,2]
    输出: 4

该题想让我们找出数组里的唯一元素,直觉上我们会使用哈希表,将重复的元素记录下来判断,但哈希表会占用额外的内存空间,如:

  1. class Solution:
  2. def singleNumber(self, nums: List[int]) -> int:
  3. h = defaultdict(int)
  4. res = 0
  5. for n in nums:
  6. h[n] += 1
  7. if h[n] > 1:
  8. res -= n
  9. else:
  10. res += n
  11. return res

如果用位运算异或,将重复元素排除,即可找出不重复的元素了,用异或的原因是:

  1. 任何数与0异或得到自身;
  2. 任何数与自身异或得到0;
  3. 异或满足结合律;

则最终实现如下:

  1. class Solution:
  2. def singleNumber(self, nums: List[int]) -> int:
  3. res = 0
  4. for n in nums:
  5. res ^= n
  6. return res

这时候是常量级别的空间复杂度。

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/109.html
邮箱:glowrypauky@gmail.com
QQ: 892413924