Single Number
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
Programmer
class Solution {
public int singleNumber(int[] nums) {
Set<Integer> s = new HashSet<Integer>();
for (int i : nums) {
if(!s.add(i)){
s.remove(i);
}
}
return s.iterator().next();
}
}
Idea
- 利用 Set 中元素的不重复性
- 往 Set 中添加元素,若此时不能继续添加就证明,将要添加的元素有重复项,是不可以添加的,所以在 Set 中删除次元素
- 最后,剩下的便是唯一的那个不重复的元素
本文由 Shuaiyin 创作,采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Sep 18,2019