【LeetCode】只出现一次的数字 IIIJava 题解

关注

发布于: 刚刚

题目描述

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例 1：
输入：nums = [1,2,1,3,2,5]输出：[3,5]解释：[5, 3] 也是有效的答案。示例 2：
输入：nums = [-1,0]输出：[-1,0]示例 3：
输入：nums = [0,1]输出：[1,0]
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/single-number-iii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是数组题目，题目要求其中恰好有两个元素只出现一次，其余所有元素均出现两次。，注意这个条件，只有两个元素只出现一次。
我们首先采用朴素解法，使用 hashMap 将所有的元素都遍历一遍并计数。然后在遍历一次 hashMap 取出出现次数是一次的元素，即为答案。
进阶解法要求的需要使用常量的空间复杂度实现，可以采用位运算解法。异或运算（xor）两个位相同为 0，相异为 1。
异或运算（xor）常见规律如下：

归零律(任何数和其自身做异或运算，结果是 0)：a xor a = 0
恒等律(任何数和 0 做异或运算，结果仍然是原来的数)：a xor 0 = a
交换律：a xor b = b xor a
结合律：a xor b xor c = a xor (b xor c ) = (a xor b) xor c

利用异或运算的性质。我们首先对 nums 中的所有元素执行异或操作，得到两个只出现一次的元素的异或值。
然后取 sum 二进制表示中为 1 的任意一位 k，sum 中的第 k 位为 1 意味着两答案的第 k 位二进制表示不同。
因为已知 sum 的第 k 位为 1，说明这两个数的第 k 位一个为 0，一个为 1，因此可以将 nums 中的元素分成两组，一组里边的元素的第 k 位都为 0，另一组都为 1，对每一组的元素分别求异或，因为其他的元素都有两个，异或的结果都为 0，所以每一组的异或结果即为答案之一。实现代码如下：

通过代码

朴素算法

class Solution {    public int[] singleNumber(int[] nums) {        Map<Integer, Integer> map = new HashMap<>();        for (int num : nums) {            map.put(num, map.getOrDefault(num, 0) + 1);        }        int[] ans = new int[2];        int j = 0;        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {            if (entry.getValue() == 1) {                ans[j++] = entry.getKey();            }        }
        return ans;    }}

复制代码

位运算解法

class Solution {    public int[] singleNumber(int[] nums) {        int sum = 0;        for (int num : nums) {            sum ^= num;        }        int k = -1;        for (int i = 31; i >= 0 && k == -1; i--) {            if (((sum >> i) & i) == 1) {                k = i;                break;            }        }
        int[] ans = new int[2];        for (int num : nums) {            if (((num >> k) & 1 )== 1) {                ans[1] ^= num;             } else {                ans[0] ^= num;             }        }
        return ans;    }}

复制代码

总结

朴素解法的时间复杂度是 O(n),空间复杂度是 O(n)
位运算解法的时间复杂度是 O(n), 空间复杂度是 O(1)
坚持算法每日一题，加油！

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/fd145251a795304adbc2fb9f6】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】只出现一次的数字 IIIJava 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论