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

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

题目：

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

思路：

上次做了两数之和的题，对hash印象还深，看到这个题的第一眼就想到hash。

遍历数组，以当前值为key，若当前表中含有该数字，value为2；若不含有，value为1，遍历完后，找表中value值为1的数字，若存在，则返回对应key；否则，不存在这样的数字。

空间复杂度是O(n)，不满足不使用额外空间的题目要求，但我想不出什么方法辣，哭了……；

代码：

class Solution {
        public int singleNumber(int[] nums) {
            //给定数组非空
            Map<Integer,Integer> map = new HashMap<Integer, Integer>();
            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如何查只出现一次的数字”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注亿速云行业资讯频道！