文档章节

【剑指offer】数组中只出现一次的数字

o
 osc_x4h57ch8
发布于 2018/04/24 15:22
字数 682
阅读 0
收藏 0

原创博文,转载请注明出处!

本题牛客网地址

代码github地址

其他面试题索引地址

 

# 题目

image

     

# 思路

 

  • 数组中有一个元素出现一次

      如果从头到尾依次异或数组中的每一个数字,结果是只出现一次的数字,因为根据异或运算的性质,任何数字和自身做异或运算的结果是0。

      举例:{4,5,5},数组中第一个元素的二进制形式为0100,第二个元素的二进制形式为0101,第三个元素的二进制形式为0101。依次对三个元素做异或运算,0100和0101异或的结果为0001,0001和0101异或的结果为0100,0100的十进制数位4。

 

  • 数组中有两个元素出现一次

      首先将数组拆分成两个子数组,每个子数组包含一个孤独元素;然后分别从子数组中找到孤独元素。数组拆分的方法从头到尾依次异或数组的每一个数字,结果的二进制表示中至少有一位是1,设结果中第一个为1的位为第n位,根据第n位是不是1,把数组中的数字分成两个子数组,第一个子数组中每个数字的第n位是1,第二个子数组中每个数字的第n位是0。

      举例:{2,4,3,6,3,2,2,5},依次对数组中的元素进行异或的结果为0010,结果中第一个为1的位是第三位,根据第三位是否为1,将数组拆分为两个子数组{2,3,6,3,2}和{4,5,5}。

 

# 代码

  1 
  2 class Solution {
  3 public:
  4     // data是数组,num1是第一个孤独数字,num2是第二个孤独数字
  5     void FindNumsAppearOnce(vector<int> data,int *num1,int *num2)
  6     {
  7         // 特殊输入检查
  8         int length = data.size();
  9         if(length < 2)
 10             return;
 11 
 12         // 对原始数组每个元素求异或
 13         int resultExclusiveOR = 0;
 14         for(int i = 0; i < length; ++i)
 15             resultExclusiveOR ^= data[i];
 16 
 17         // 在异或结果中寻找第一个为1的位
 18         unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);
 19 
 20         // 寻找只出现一次的数字num1,num2
 21         *num1 = *num2 = 0;
 22         for(int j = 0; j < length; j++)
 23             if(IsBit1(data[j], indexOf1))
 24                 *num1 ^= data[j];
 25             else
 26                 *num2 ^= data[j];
 27     }
 28 private:
 29 
 30     // 找到二进制数num第一个为1的位数,比如0010,第一个为1的位数是2。
 31     unsigned int FindFirstBitIs1(int num){
 32         unsigned int indexBit = 0;
 33         // 只判断一个字节的
 34         while((num & 1) == 0 && (indexBit < 8 * sizeof(unsigned int))){
 35             num = num >> 1;
 36             indexBit++;
 37         }
 38         return indexBit;
 39     }
 40 
 41     // 判断第indexBit位是否为1
 42     bool IsBit1(int num, unsigned int indexBit){
 43         num = num >> indexBit;
 44         return (num & 1);
 45     }
 46 };

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

如何在Ruby中生成随机字符串 - How to generate a random string in Ruby

问题: I'm currently generating an 8-character pseudo-random uppercase string for "A" .. "Z": 我目前正在为“ A” ..“ Z”生成一个8个字符的伪随机大写字符串: value = ""; 8.times{......

法国红酒甜
54分钟前
20
0
Python中的mkdir -p功能[重复] - mkdir -p functionality in Python [duplicate]

问题: This question already has an answer here: 这个问题在这里已有答案: How can I safely create a nested directory? 如何安全地创建嵌套目录? 25 answers 25个答案 Is there a way...

技术盛宴
今天
15
0
原价500元的认证证书,限时免费考取!

本文作者:y****n 百度云智学院致力于为百度ABC战略(人工智能、大数据、云计算)提供人才生态体系建设,包括基于百度ABC、IoT的课程体系,整合百度优势技术能力的深度学习技术、Apollo无人车...

百度开发者中心
昨天
17
0
在virtualenv中使用Python 3 - Using Python 3 in virtualenv

问题: Using virtualenv , I run my projects with the default version of Python (2.7). 使用virtualenv ,我使用默认版本的Python(2.7)运行项目。 On one project, I need to use Pyth......

富含淀粉
今天
16
0
Python的__init__和self是做什么的? - What __init__ and self do on Python?

问题: I'm learning the Python programming language and I've came across something I don't fully understand. 我正在学习Python编程语言,遇到了一些我不太了解的东西。 In a method ......

javail
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部