当前位置: 首页 > article >正文

56 - I. 数组中数字出现的次数


comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9856%20-%20I.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E6%95%B0%E5%AD%97%E5%87%BA%E7%8E%B0%E7%9A%84%E6%AC%A1%E6%95%B0/README.md

面试题 56 - I. 数组中数字出现的次数

题目描述

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

 

示例 1:

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]

示例 2:

输入:nums = [1,2,10,4,1,4,3,3]
输出:[2,10] 或 [10,2]

 

限制:

  • 2 <= nums.length <= 10000

 

解法

方法一:位运算

由于数组中除了两个数字之外,其他数字都出现了两次,因此对数组中的所有数字进行异或运算,得到的结果即为两个只出现一次的数字的异或结果。

由于这两个数字不相等,因此异或结果中至少存在一位为 1 1 1。我们通过 lowbit 运算找到异或结果中最低位的 1 1 1,并将数组中的所有数字按照该位是否为 1 1 1 分为两组,这样两个只出现一次的数字就被分到了不同的组中。

对两个组分别进行异或运算,即可得到两个只出现一次的数字。

时间复杂度 O ( n ) O(n) O(n),其中 n n n 为数组长度。空间复杂度 O ( 1 ) O(1) O(1)

https://www.acwing.com/video/2852/
在这里插入图片描述

Python3
# reduce 函数将一个二元函数(即接受两个参数的函数)逐步应用到可迭代对象的项上,从左到右,直到将可迭代对象缩减为一个单一的值。
 from functools import reduce
class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        xs = reduce(xor, nums) #所有元素的异或结果=两个不相等数的异或结果a&b
        
        a = 0
        lb = xs & -xs  #得到最后一个位为1对应的数: 两个不相等数的异或结果a&b ≠ 0,说明至少有一位为1
        for x in nums:
            if x & lb:  #核心1:这样运算 只会剩下 第k位为1的a , 其他次数为2的数异或为0
                a ^= x
        b = xs ^ a   #核心2:获得a后,xs^a 会将a对应的位抹零,剩下的位就属于b
        return [a, b]
Java
class Solution {
    public int[] singleNumbers(int[] nums) {
        int xs = 0;
        for (int x : nums) {
            xs ^= x;
        }
        int lb = xs & -xs;
        int a = 0;
        for (int x : nums) {
            if ((x & lb) != 0) {
                a ^= x;
            }
        }
        int b = xs ^ a;
        return new int[] {a, b};
    }
}
C++
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int xs = 0;
        for (int& x : nums) {
            xs ^= x;
        }
        int lb = xs & -xs;
        int a = 0;
        for (int& x : nums) {
            if (x & lb) {
                a ^= x;
            }
        }
        int b = xs ^ a;
        return {a, b};
    }
};
Go
func singleNumbers(nums []int) []int {
	xs := 0
	for _, x := range nums {
		xs ^= x
	}
	lb := xs & -xs
	a := 0
	for _, x := range nums {
		if x&lb != 0 {
			a ^= x
		}
	}
	b := xs ^ a
	return []int{a, b}
}
TypeScript
function singleNumbers(nums: number[]): number[] {
    let xs = 0;
    for (const x of nums) {
        xs ^= x;
    }
    const lb = xs & -xs;
    let a = 0;
    for (const x of nums) {
        if (x & lb) {
            a ^= x;
        }
    }
    const b = xs ^ a;
    return [a, b];
}
JavaScript
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumbers = function (nums) {
    let xs = 0;
    for (const x of nums) {
        xs ^= x;
    }
    const lb = xs & -xs;
    let a = 0;
    for (const x of nums) {
        if (x & lb) {
            a ^= x;
        }
    }
    const b = xs ^ a;
    return [a, b];
};
C#
public class Solution {
    public int[] SingleNumbers(int[] nums) {
        int xs = 0;
        foreach(int x in nums) {
            xs ^= x;
        }
        int lb = xs & - xs;
        int a = 0;
        foreach(int x in nums) {
            if ((x & lb) != 0) {
                a ^= x;
            }
        }
        int b = xs ^ a;
        return new int[] {a, b};
    }
}
Swift
class Solution {
    func singleNumbers(_ nums: [Int]) -> [Int] {
        var xorSum = 0
        for num in nums {
            xorSum ^= num
        }

        let lowBit = xorSum & -xorSum
        var a = 0
        for num in nums {
            if (num & lowBit) != 0 {
                a ^= num
            }
        }

        let b = xorSum ^ a
        return [a, b]
    }
}

http://www.kler.cn/a/305084.html

相关文章:

  • 【教程】华南理工大学国际校区宿舍门锁声音设置
  • Stored procedures in PostgreSQL
  • Java-Redisson分布式锁+自定义注解+AOP的方式来实现后台防止重复请求扩展
  • 【ubuntu】单进程申请4GB内存
  • 【C++】 list 与 string 基础与实现字符串操作
  • 招聘app开发,人才招聘、求职首要方式
  • CAN总线-STM32上CAN外设
  • ansible_find模块
  • 计算机四级数据库原理考试大纲.md
  • 37. MyBatis-Plus是什么?它与MyBatis的主要区别是什么?
  • 音视频开发常见的开源项目汇总
  • 新挂载的磁盘不能创建文件
  • 数据清洗-缺失值填充-随机森林填充
  • 【Django】Django Class-Based Views (CBV) 与 DRF APIView 的区别解析
  • Python基础语法(1)上
  • 基于微信小程序的图书馆预约占座系统
  • 【vscode】 快速生成react组件
  • uniapp小程序,使用腾讯地图获取定位
  • 监听html元素是否被删除,删除之后重新生成被删除的元素
  • PHP悦读随行一键借阅图书小程序
  • 【hot100-java】【环形链表】
  • 代理IP设置后IP不变?可能的原因及解决方法
  • 网站优化与服务器:性能提升的双重奏
  • Orchestrator 与 Mysql 8.0 的兼容性
  • NLP中文本生成任务
  • 【系统规划与管理师】【案例分析】【考点】【答案篇】第6章 IT服务运营管理