LeetCode如何查只出现一次的数字
这篇文章主要介绍LeetCode如何查只出现一次的数字，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！
我们提供的服务有：成都网站制作、网站建设、微信公众号开发、网站优化、网站认证、太原ssl等。为上千余家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的太原网站制作公司
题目：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
思路：
上次做了两数之和的题，对hash印象还深，看到这个题的第一眼就想到hash。
遍历数组，以当前值为key，若当前表中含有该数字，value为2；若不含有，value为1，遍历完后，找表中value值为1的数字，若存在，则返回对应key；否则，不存在这样的数字。
空间复杂度是O(n)，不满足不使用额外空间的题目要求，但我想不出什么方法辣，哭了......；
代码：
class Solution {
public int singleNumber(int[] nums) {
//给定数组非空
Map map = new HashMap();
for(int i:nums)
{
if(map.containsKey(i))
{
map.put(i,2);
}
else
map.put(i,1);
}
for(int j:map.keySet())
{
if(map.get(j) == 1)
return j;
}
return -1;
}
} demo：
输入：[2,2,1] 输出：1
输入：[4,1,2,1,2] 输出：4
运行结果：
官方解答
解
异或位运算
性质1：如果对0和二进制位做异或运算，得到的仍是这个二进制位。
性质2：如果我们对相同的二进制位做异或运算，返回的结果是0。
性质3：异或运算满足交换律和结合律。
思路
代码
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for (int num : nums) {
single ^= num;
}
return single;
}
}复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
复习
位运算虽然不是很常见，但是适当的使用可以大量减少开销。
Java中常用的位运算
&：按位与。
|：按位或。
~：按位非。
^：按位异或。
按位与
| 操作数1 | 0 | 0 | 1 | 1 |
|---|---|---|---|---|
| 操作数2 | 0 | 1 | 0 | 1 |
| 按位与 | 0 | 0 | 0 | 1 |
按位或
| 操作数1 | 0 | 0 | 1 | 1 |
|---|---|---|---|---|
| 操作数2 | 0 | 1 | 0 | 1 |
| 按位或 | 0 | 1 | 1 | 1 |
按位非
| 操作数 | 0 | 1 |
|---|---|---|
| 按位或 | 1 | 0 |
按位异或
| 操作数1 | 0 | 0 | 1 | 1 |
|---|---|---|---|---|
| 操作数2 | 0 | 1 | 0 | 1 |
| 按位异或 | 0 | 1 | 1 | 0 |
以上是“LeetCode如何查只出现一次的数字”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注创新互联行业资讯频道！
网页名称：LeetCode如何查只出现一次的数字
路径分享：http://shouzuofang.com/article/pgeseh.html