题目描述: 给一个数组, 数组中只有一个数字出现了一次, 其他的数字都出现了两次, 找到这个只出现一次的数字
- Given a non-empty array of integers, every element appears twice except for one. Find that single one.
- Note:
- Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
- Example 1:
- Input: [2,2,1]
- Output: 1
- Example 2:
- Input: [4,1,2,1,2]
- Output: 4
思路:
通过异或运算来消除出现两次的数字, 从而最终得到只出现一次的数字.
代码实现:
- class Solution {
- public int singleNumber(int[] nums) {
- // 思路:
- // 采用异或运算, 数组中只有一个数出现了一次, 其他的都出现了两次
- // 那么可以通过异或, 把所有出现偶数次的数字给消除, 最后剩下的只有那一个出现一次的数字
- int res = nums[0];
- for(int i =1; i<nums.length; i++){
- res ^= nums[i];
- }
- return res;
- }
- }
来源: http://www.bubuko.com/infodetail-3357160.html