算法面试题-奇数次的数
2021/10/31 22:14:24
本文主要是介绍算法面试题-奇数次的数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:
(1)一组数中,只有一个数出现了奇数次,其余数都出现偶数次,在O(N)的时间复杂度中找出该数
(2)一组数中,有两个数出现了奇数次,其余数都出现偶数次,在O(N)的时间复杂度中找出这两个数
分析:
(1)假设eor = 0,将eor分别与该数组中的全部数进行异或,最后得到的结果就是该数。比如数组为[2,1,3,1,2], eor = 0 ^ 2 ^ 1 ^ 3 ^ 1 ^ 2 = 1 ^ 1 ^ 2 ^ 2 ^ 3 = 0 ^ 0 ^ 3 = 3
(2)假设eor = 0,将eor分别与该数组中的全部数进行异或,最后得到的结果为a^b(假设这两个数为出现奇数次的数)。此时的eor肯定有至少有一个二进位是1(因为a不等于b),假设是第8个二进制位为1, 可以将所有数分为第8位为1和为0的, a和b肯定分别属于这两个类。假设eor’= 0, 将eor’和第8位为1的数分别去异或, 出现偶数次的数依旧不会干扰结果, 最后得到的eor’=a(如果a的第8位是1)。再将eor ^ eor’ = a^b^a = b, 此时a和b都求到了
代码实现:
public static void printOddTimesNum2(int[] arr) { /** * 题2 */ int eor = 0, eor_dot = 0; for (int curNum : arr) { eor ^= curNum; } // eor = a ^ b eor != 0 eor二进制位上必有一个是1 int rightOne = eor & (~eor + 1); // *取出eor最右边的1, 假设eor=1011, ~eor=0100, ~eor+1=0101, eor & (~eor + 1) = 0001 for (int curNum : arr) { if ((curNum & rightOne) == 1) { //将eor_dot和在rightOne位置上为1的数进行异或 eor_dot ^= curNum; } } System.out.println(eor_dot + " " + (eor ^ eor_dot)); } public static void printOddTimesNum1(int[] arr) { /** * 题1 */ int eor = 0; for (int cur : arr) { eor ^= cur; } System.out.println(eor); }
tips:
要取出eor二进制最右边的1, 可以采用以下代码实现。假设eor=1011,~eor=0100, ~eor+1=0101, eor & (~eor + 1) = 0001
int rightOne = eor & (~eor + 1)
这篇关于算法面试题-奇数次的数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29DataGrip使用ssh连接数据库的操作流程
- 2024-05-28SpringBoot3.2更新声明!
- 2024-05-28中外程序员到底有啥区别?
- 2024-05-25外企也半夜发布上线吗?
- 2024-05-24鸿蒙原生应用再新丁!芒果TV 入局鸿蒙
- 2024-05-22基本概念
- 2024-05-22检索数据
- 2024-05-22排序数据
- 2024-05-22基础过滤数据
- 2024-05-22通过逻辑操作符过滤数据