【每日一题Day349】LC260只出现一次的数字 III | 位运算

简介: 【每日一题Day349】LC260只出现一次的数字 III | 位运算

只出现一次的数字 III【LC260】

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

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

思路

image.png

实现

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums){
            xor  ^= num;
        }
        // 找到第一位为1的位置
        int bit1 = 0;
        for (int i = 30; i >= 0; i--){
            if (((xor >> i) & 1) == 1){
                bit1 = i;
                break;
            }
        }
        int a = 0, b = 0;
        for (int num : nums){
            if (((num >> bit1) & 1) == 1){
                a ^= num;
            }else{
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}

复杂度

时间复杂度:O ( n )

空间复杂度:O ( 1 )

目录
相关文章
|
7月前
|
算法
【每日一题Day347】LC136只出现一次的数字 | 位运算
【每日一题Day347】LC136只出现一次的数字 | 位运算
51 0
|
7月前
【每日一题Day202】LC1015可被 K 整除的最小整数 | 模运算
【每日一题Day202】LC1015可被 K 整除的最小整数 | 模运算
67 2
|
7月前
【每日一题Day194】LC970强整数 | 枚举
【每日一题Day194】LC970强整数 | 枚举
38 0
|
7月前
【每日一题Day268】LC415字符串相加 | 模拟
【每日一题Day268】LC415字符串相加 | 模拟
48 0
|
7月前
【每日一题Day290】LC1281整数的各位积和之差 | 模拟
【每日一题Day290】LC1281整数的各位积和之差 | 模拟
43 0
|
7月前
【每日一题Day366】LC2103环和杆 | 状态压缩
【每日一题Day366】LC2103环和杆 | 状态压缩
48 0
|
7月前
【每日一题Day359】LC2520统计能整除数字的位数 | 数学模拟
【每日一题Day359】LC2520统计能整除数字的位数 | 数学模拟
52 0
|
7月前
|
机器学习/深度学习
【每日一题Day263】LC2544交替数字和 | 数学
【每日一题Day263】LC2544交替数字和 | 数学
49 0
|
7月前
|
存储 人工智能 算法
【每日一题Day348】LC137只出现一次的数字Ⅱ | 状态转移
【每日一题Day348】LC137只出现一次的数字Ⅱ | 状态转移
49 0
|
7月前
【每日一题Day169】LC1107负二进制转换 | 模拟进位 位运算
【每日一题Day169】LC1107负二进制转换 | 模拟进位 位运算
35 1