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

出现一次的数字(其他数字出现三次,两次)

 位运算的知识点:
 

异或运算具有以下几个重要性质
交换律:a ^ b = b ^ a
结合律:a ^ (b ^ c) = (a ^ b) ^ c
任何数与0异或等于它本身:a ^ 0 = a
任何数与自身异或等于0:a ^ a = 0
对于数组中所有元素进行异或运算,由于相同的元素异或结果为0,所以最终结果等于a和b异或的结果:result = a ^ b。

在result中找到任意为1的位(可以是a和b在二进制表示中不同的任意位),我们可以通过result & -result来得到。这样做的目的是找到a和b在该位上不同的地方,便于将它们分成两组。

根据该位上是0还是1,我们可以将数组中的所有元素分成两组,一组是在该位上为1的元素,另一组是在该位上为0的元素。因为a和b在这一位上不同,所以它们会被分在不同的组中。

然后,分别对这两组元素进行异或运算,得到两个结果,分别是a和b在该组内的异或结果。
最终,返回这两个结果,就得到了只出现一次的两个元素a和b

1 3 1 2 3 5
int onceElement = 0;
for(int i = 0;i < arr.length;i++){
    onceElement = onceElement^arr[i]
}
//onceElement = 10(2*5)
int span = 1;
while(onceElement & span == 0){
    span <<= 1
}

int group1,group2 = 0;
for(int i = 0;i < arr.length;i++){
    if(arr[i] & span){
        group1 ^= arr[i];
    }else{
        group2 ^= arr[i];
    }
}
System.out.println(group1 + "\t" + group2);

 

或运算的最小翻转次数:

http://www.lryc.cn/news/107783.html

相关文章:

  • Rust- 智能指针
  • 什么是微服务
  • 无人机电力巡检方案在电网安全与维护中的应用
  • 网络工程师 快速入门
  • Linux系统vim查看文件中文乱码
  • BladeX框架开源-工作-笔记-Docker部署-Jenkins配置
  • Modbus tcp转ETHERCAT网关modbus tcp/ip协议
  • RK356x Android11更换默认的Launcher
  • Python 操作 MySQL 数据库
  • 脑电信号处理与特征提取——6.运用机器学习技术和脑电进行大脑解码(涂毅恒)
  • 腾讯云COS+PicGO+截图工具+Obsidian+Typora+蚁小二:打造丝滑稳定的Markdown写作和分发环境
  • LeetCode--HOT100题(18)
  • ES6的语法兼容IE浏览器
  • 【opencv学习】鼠标回调函数、鼠标控制画矩形
  • Typescript面试题
  • GB28181智能安全帽方案探究及技术实现
  • 【css】解决元素浮动溢出问题
  • SOC FPGA之流水灯设计
  • 无涯教程-Lua - Iterators(迭代器)
  • HTML+CSS+JavaScript:实现B站评论发布效果
  • 实战 - 利用 ThreadLocal 线程局部变量实现数据缓存
  • wxwidgets Ribbon使用简单实例
  • 2023年第四届“华数杯”数学建模思路 - 案例:最短时间生产计划安排
  • LeetCode404. 左叶子之和
  • Nginx 高性能内存池 ----【学习笔记】
  • iOS--frame和bounds
  • docker logs 使用说明
  • Ceph入门到精通-Ceph PG状态详细介绍(全)
  • 【数据结构】二叉树、二叉搜索树、平衡二叉树、红黑树、B树、B+树
  • 【JVM】(二)深入理解Java类加载机制与双亲委派模型