LeetCode 260. Single Number III
题目来源:https://leetcode.com/problems/single-number-iii
题目难度:Medium
解答1[Java]:
核心思想
假设两个只出现一次的数为 a 和 b,先把所有的数做异或,这样的得到的结果为 a^b
,如果 a^b
的二进制形式的某一位是 1,说明 a 和 b 两个数在这一位上不同,可以根据这一位把所有的数分为两个组,一组是这一位为 1 的,一组是这一位为 0。如果两个数相同,那么这样两个数肯定会分到同一组。但是 a 和 b 会被分到不同的组。这样,对任意一组的全部数字执行异或操作,那么就会得到 a 和 b 其中的一个。再用其中的一个和 a^b
做异或运算就可以得到另外一个数字。
代码
1 | class Solution { |
解答2[Java]:
核心思想
使用 HashMap 计数。
代码
1 | import java.util.*; |
解答3[Java]:
核心思想
对一个数,如果不在 set 中,就放进去,如果已经在 set 中,说明是成对的,就把原来的也移出去,最后剩下的就是不同的两个数。
代码
1 | import java.util.HashSet; |
补充
异或的基本运算:n^0 = n
。