Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
这个题,头脑爆炸💥,如果是没怎么接触过异或运算的话,想破脑袋也想不到这样的解法。这个解法主要利用了一个异或运算的性质,即 x ⊕ x = 0
,将数组中所有的数字都异或运算之后,最终的值自然就是落单的那个数了。
/*
* 136. Single Number
* https://leetcode.com/problems/single-number/
* https://realneo.me/136-single-number/
*/
public class SingleNumber {
public static void main(String[] args) {
SingleNumber solution = new SingleNumber();
int[] nums;
nums = new int[]{2, 2, 1};
System.out.println(solution.singleNumber(nums));
nums = new int[]{4, 1, 2, 1, 2};
System.out.println(solution.singleNumber(nums));
}
private int singleNumber(int[] nums) {
int x = 0;
for (int i : nums)
x ^= i;
return x;
}
}