剑指offer--一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

朱雀 2022-05-22 06:09 137阅读 0赞

#### 尝试说明大家普遍使用的一种方法：利用位运算来实现。 ####

三步走：

1.**首先将数组元素依次异或，得到值resultExclusiveOR,接下来要利用这个数字****将原数组分为两部分。**

2.利用子函数FindFirstBitIs1()来找FindFirstBitIs1中第一次出现1的位，假设为b位。

3.接下来就是利用函数IsBit()来实现区分b位为1的一组，不为1的是另一组。

`class` `Solution {`

`public` `:`

`    ` `void` `FindNumsAppearOnce(vector<` `int` `> data,` `int` `* num1,` `int` `* num2) {`

`        ` `if` `(data.size() < 2)`

`            ` `return` `;`

`         `

`        ` `int` `resultExclusiveOR = 0;`

`        ` `for` `(` `int` `i = 0; i < data.size(); i++){`

`            ` `resultExclusiveOR ^= data[i];`

`        ` `}`

`         `

`        ` `unsigned ` `int` `indexOf1 = FindFirstBitIs1(resultExclusiveOR);`

`         `

`        ` `*num1 = *num2 = 0;`

`        ` `for` `(` `int` `j = 0; j < data.size(); j++){`

`            ` `if` `(IsBit1(data[j], indexOf1))`

`                ` `*num1 ^= data[j];`

`            ` `else`

`                ` `*num2 ^= data[j];`

`        ` `}`

` `

`    ` `}`

`     `

`    ` `unsigned ` `int` `FindFirstBitIs1(` `int` `num){`

`        ` `int` `indexBit = 0;`

`        ` `while` `(((num & 1) == 0) && (indexBit < 8*` `sizeof` `(` `int` `))){`

`            ` `num = num >> 1;`

`            ` `indexBit++;`

`        ` `}`

`         `

`        ` `return` `indexBit;`

`    ` `}`

`     `

`    ` `bool` `IsBit1(` `int` `num, unsigned ` `int` `indexBit){`

`        ` `num = num >> indexBit;`

`        ` `return` `(num&1);`

`    ` `}`

`     `

`};`

怎么实现的呢，刚开始我也是一头雾水，但是仔细看一会发现，例如，2，3,4,4,5,5，二进制代码依次为10,11,100,100,101,101。将他们依次异或（^）后，结果为01，显然相同的4和4,5和5根本不影响不相同的数2和3之前的异或，这是一点，假如2,4,4,5,5.异或之后结果10，即2；3,4,4,5,5。异或之后结果为11，即3,；好了这一个异或解决了两个问题，找到单独存在的数和如何提出来单独的数，只要把单独存在且不同的两个数分到两个数组里然后异或，结果就是我们要的，怎么分数组，整体数组异或结果位出现1可以说明原来两个不同的数在这一位是不同的，那这个突破点就找到了，只要从右到左找到第一个1所在位，然后按照在这一位是1为标准划分为两个数组就可以了。举个例子更形象，7和10，二进制依次为0111和1010，异或结果为1101，只要把二进制第一位是1的分到A数组，不是1的分到B数组，就自然把7和10分到两个数组了。

发表评论取消回复

表情：

评论列表（有 0 条评论，137人围观）

还没有评论，来说两句吧...

相关阅读

相关数组中只出现一次【两次】的数字

题目描述一个整型数组里除了两个数字之外，其他的数字都出现了一次【或两次】。请写程序找出这两个只出现一次的数字。只出现一次集合判断是否重复 Set.ad

素颜马尾好姑娘i/ 2022年12月06日 15:51/ 0 赞/ 150 阅读

相关编程笔试(解析及代码实现)：求不重复数字之和给定一组整型数字，里面有且仅有两个数字值出现了一次，其他的数字都出现了两次。请写出程序求出这两个只出现了一次的数字之和

编程笔试(解析及代码实现)：求不重复数字之和给定一组整型数字，里面有且仅有两个数字值出现了一次，其他的数字都出现了两次。请写出程序求出这两个只出现了一次的数字之和目录题

ゝ一纸荒年。/ 2022年09月11日 06:22/ 0 赞/ 63 阅读

相关求数组中只出现一次的两个数字

文章目录一、求数组中只出现一次的两个数字 1.题目描述 2.题目链接 3.解题方法一、求数组中

缺乏、安全感/ 2022年08月30日 11:42/ 0 赞/ 139 阅读

相关一个数组中只有两个数字是出现一次，其他所有数字都出现了两次，找出这两个数字，编程实现

include<string.h> include<stdlib.h> include<stdio.h> void Find_Two_Numbe

布满荆棘的人生/ 2022年07月15日 09:42/ 0 赞/ 126 阅读

相关【剑指offer】面试题56（1）：数组中只出现一次的两个数字

题目一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。思路有空再补上 0.0 代码 /

素颜马尾好姑娘i/ 2022年06月11日 07:09/ 0 赞/ 79 阅读

相关剑指offer--一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

尝试说明大家普遍使用的一种方法：利用位运算来实现。三步走： 1.首先将数组元素依次异或，得到值resultExclusiveOR,接下来要利用这个数字将原数组分为两部

朱雀/ 2022年05月22日 06:09/ 0 赞/ 138 阅读

相关数组中只出现一次的两个数字【python】

题目描述一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。 -------------------- 首先考虑，如果一个数

绝地灬酷狼/ 2022年04月02日 03:02/ 0 赞/ 191 阅读

相关一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。找出这两个数字，编程实现。

一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。找出这两个数字，编程实现。 int main() { int arr[] = {

谁践踏了优雅/ 2022年02月21日 12:02/ 0 赞/ 169 阅读

相关 .一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。找出这两个数字，编程实现。

.一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。找出这两个数字，编程实现。 . int main()\{ char arr\[\] = \{1,

本是古典何须时尚/ 2021年10月29日 23:24/ 0 赞/ 203 阅读

相关一个数组中，只有一个数字仅出现一次，其他数字均出现两次，找出这个数字

要求：不借助任何空间我们知道:a^0 = a,a^a = 0，因此这里可以借助异或运算可以实现。具体实现如下： public class SingleNu

一时失言乱红尘/ 2021年09月26日 14:54/ 0 赞/ 235 阅读