CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

    • 整数理论基础
    • 整数除法
    • 二进制加法
    • 剑指 Offer 15 - 二进制中 1 的个数
    • 前 n 个数字二进制中 1 的个数
    • 只出现一次的数字
    • 只出现一次的数字II
    • 只出现一次的数字 III
      • 📃 题目描述
      • 🔔 解题思路
      • 💥 复杂度分析
    • 剑指 Offer 39 - 数组中出现次数超过一半的数字
    • 剑指 Offer 16 - 数值的整数次方:快速幂模板
    • 剑指 Offer 43 - 1~n 整数中 1 出现的次数
  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 整数 and 位运算
小牛肉
2022-09-07
目录

只出现一次的数字 III

# 📃 题目描述

题目链接:260. 只出现一次的数字 III (opens new window)

# 🔔 解题思路

第一步:

把所有的元素进行异或操作,最终得到一个异或值。因为是不同的两个数字,所以这个值必定不为 0;

   int xor = 0;
    for (int num : nums) {
        xor ^= num;
    } 

第二步:

取异或值中随便一个二进制位为 1 的数字作为 mask,这两个只出现一次的数字在这一位上一定是不同的。

if (((sum >> i) & 1) == 1) {
	k = i;
	break;
}

第三步:

通过与这个 mask 进行 & 操作,如果为 0 的分为一个数组,为 1 的分为另一个数组。这样就把问题降低成了:“有一个数组每个数字都出现两次,有一个数字只出现了一次,求出该数字”。对这两个子问题分别进行全异或就可以得到两个解。也就是最终的数组了

class Solution {
    public int[] singleNumber(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i ++) {
            sum ^= nums[i];
        }

        int k = 0;
        for (int i = 0; i < 32; i ++) {
            if (((sum >> i) & 1) == 1) {
                k = i;
                break;
            }
        }

        int[] res = new int[2];
        // 对第 k 位分别为 0 和 1 的元素分别求异或和(两答案必然会被分到不同的组)
        for (int num : nums) {
            if (((num >> k) & 1) == 1) {
                res[1] ^= num;
            }
            else {
                res[0] ^= num;
            }
        }

        return res;
    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
只出现一次的数字II
剑指 Offer 39 - 数组中出现次数超过一半的数字

← 只出现一次的数字II 剑指 Offer 39 - 数组中出现次数超过一半的数字→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式