题目
Given a non-empty array of integers nums
, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1] Output: 1
Example 2:
Input: nums = [4,1,2,1,2] Output: 4
Example 3:
Input: nums = [1] Output: 1
Constraints:
1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
- Each element in the array appears twice except for one element which appears only once.
思路
最简单思路当然是用HashMap来处理。但是HashMap的话,空间复杂度就是O(n),而不是O(1)。
该题需要利用数字A异或它本身等于0
。不刷题根本想不到。。
代码
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num: nums) {
result ^= num;
}
return result;
}
}
Be First to Comment