• LeetCode_位运算_中等_137.只出现一次的数字 II


    1.题目

    给你一个整数数组 nums ,除某个元素仅出现一次外,其余每个元素都恰出现三次 。请你找出并返回那个只出现了一次的元素。

    示例 1:
    输入:nums = [2,2,3,2]
    输出:3

    示例 2:
    输入:nums = [0,1,0,1,0,1,99]
    输出:99

    提示:
    1 <= nums.length <= 3 * 104
    -231 <= nums[i] <= 231 - 1
    nums 中,除某个元素仅出现一次外,其余每个元素都恰出现三次

    进阶:你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?

    来源:力扣(LeetCode)
    链接:https://leetcode.cn/problems/single-number-ii

    2.思路

    (1)哈希表
    如果使用额外空间的话,比较容易想到的是使用哈希表,先将数组中的所有元素添加到 hashMap 中(键/值为元素值/该元素出现的次数),然后再在哈希表中找出只出现了一次的元素并将其返回即可。

    (2)哈希集合
    先用集合 hashSet 来存储数组 nums 中出现的所有元素,并且计算数组 nums 中的所有元素之和。又由于集合元素的无重复性,所以集合 hashSet 中的所有元素之和的三倍就是数组 nums 中每个元素出现三次的情况下的元素之和。又由题目可知,数组 nums 中只有一个元素出现一次,其余元素都出现三次,所以只出现一次的元素值 = (nums 中所有非重复元素之和 * 3 - nums的所有元素之和) / 2。不过在编写时需要注意 int 整数溢出的问题!

    (3)位运算
    使用长度为 32 的数组 cnt 来记录数组 nums 中所有元素对应的二进制位的每一位出现的 1 的总次数,然后再对数组 cnt 中的每一个元素值进行 mod 3 操作,将拼接出的结果即为数组 nums 中只出现一次的元素。为了方便理解,以下面的例子来介绍:

    (1) 假设数组 nums = {2, 2, 3, 2, 5, 5, 5},其中的元素对应的二进制数分别为:
    00...010
    00...010
    00...011
    00...010
    00...101
    00...101
    00...101
    
    (2) 通过计算可知 cnt = {0, 0, ..., 3, 4, 4},以 cnt[31] = 4 为例,它表示 2, 2, 3, 2, 5, 5, 5 对应的二进制数的最低位一共有 41
    
    (3) 由于数组 nums 中,除某个元素仅出现一次外,其余每个元素都恰出现三次,那么这说明出现三次的元素所对应的二进制数的每一位也出现了 3 次,
    这反应到数组 cnt 中的情况就是 cnt[i] == k * 3 + 1/0,其中 k 表示当二进制位为 1 的且出现三次的元素的个数,所以对数组 cnt 中的每一个元素
    进行 mod 3 操作后得到 {0, 0, ..., 0, 1, 1},显然将 0, 0, ..., 1, 1 拼接后得到的数为只出现一次的元素所对应的二进制数,即 Nums 中的 3
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    另外,该算法的时间复杂度为 O(n),空间复杂度为 O(1)。

    相似题目:
    LeetCode_位运算_简单_136.只出现一次的数字

    3.代码实现(Java)

    //思路1————哈希表
    class Solution {
        public int singleNumber(int[] nums) {
            HashMap<Integer, Integer> hashMap = new HashMap<>();
            for (int num : nums) {
                hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
            }
            for (Integer i : hashMap.keySet()) {
                if (hashMap.get(i) == 1) {
                    return i;
                }
            }
            return -1;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    //思路2————哈希集合
    class Solution {
        public int singleNumber(int[] nums) {
            HashSet<Integer> hashSet = new HashSet<>();
            long sum = 0;
            for (int num : nums) {
                hashSet.add(num);
                //计算数组 nums 中所有元素之和
                sum += (long)num;
            }
            long setSum = 0;
            for (Integer num : hashSet) {
                //计算数组 nums 中所有非重复元素之和
                setSum += (long)num;
            }
            return (int)((3 * setSum - sum) / 2);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    //思路3————位运算
    class Solution {
        public static int singleNumber(int[] nums) {
            int res = 0;
            //记录下所有数值的每一位共出现了多少次 1
            int[] cnt = new int[32];
            for (int num : nums) {
                for (int i = 0; i < 32; i++) {
                    /*
                        num >> i: num 对应的二进制数的所有二进制为均向右移 i 位
                        (num >> i) & 1: 获取 num >> i 的二进制数的最低位
                    */
                    if (((num >> i) & 1) == 1) {
                        cnt[i]++;
                    }
                }
            }
            for (int i = 0; i < 32; i++) {
                if ((cnt[i] % 3 & 1) == 1) {
                	//拼接结果
                    res += (1 << i);
                }
            }
            return res;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
  • 相关阅读:
    如何用 Elasticsearch 实现 Word、PDF,TXT 文件的全文内容检索?
    深究数据库E-R模型设计
    单细胞文献学习(part5)--Using Cell-to-Cell Variability— A New Era in Molecular Biology
    寄售抢画字画拍卖-数字藏品竞拍-拍溢价系统古玩文物寄售源码系统
    开发知识点-Django
    js 小数相加 精度
    Java 算法篇-链表的经典算法:判断回文链表、判断环链表与寻找环入口节点(“龟兔赛跑“算法实现)
    工作中,Oracle常用函数
    SQL查询比较慢,如何进行排查?如何进行SQL优化?
    Vue2基础用法及案例
  • 原文地址:https://blog.csdn.net/weixin_43004044/article/details/126020515