LeetCode如何查只出现一次的数字

这篇文章主要介绍LeetCode如何查只出现一次的数字，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

题目：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

思路：

上次做了两数之和的题，对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中常用的位运算

&：按位与。

|：按位或。

~：按位非。

^：按位异或。

按位与

按位或

按位非

按位异或

以上是"LeetCode如何查只出现一次的数字"这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注行业资讯频道！