Given an 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?
Solution1：持續(xù)累積異或
思路：結(jié)果就是that single one，appear twice 的會(huì)異或成0
Time Complexity: O(N) Space Complexity: O(1)
Solution2：hashset
Time Complexity: O(N) Space Complexity: O(N)
Solution1 Code：
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for(int i = 0; i < nums.length; i++)
result ^= nums[i];
return ans;
}
}
Solution2 Code：
class Solution {
public int singleNumber(int[] nums) {
HashSet<Integer> set = new HashSet<Integer>();
for(int i = 0; i < nums.length; i++)
if(!set.remove(nums[i])) {
set.add(nums[i]);
}
return set.iterator().next();
}
}
