题目
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路
我们直到异或的性质:
任何一个数字异或他自己都等于0.
所以说我们如果从头到尾依次异或每一个数字,那么最终的结果刚好只出现一次的数字,因为成对出现的两次的数字全部在异或中抵消了。
这道题中有两个数字只出现一次。这样的话我们得到的结果就是这两个数字的异或结果。因此我们想办法把原数组分成两个子数组,使得每个子数组包含一个只出现一次的数字。这样我们就可以对这两个子数组分别异或,就能得到两个只出现一次的数字。
现在问题是怎样把原数组分成两个子数组,使得每个子数组包含一个只出现一次的数字?
由于异或的结果肯定是那两个只出现一次的数字的异或结果,所以异或结果肯定不为0,也就是说这个结果二进制表示中至少有一位是1。我们可以找到第一个为1的下标位置(记为第n位)作为划分数组的依据。第一个子数组中每个数的第n位为1,第二个子数组的每个数的第n位为0。对于出现两次的数肯定分在同一个子数组中。那两个只出现一次的数字分别分在不同的子数组中。
假设数组为{2,4,3,6,3,2,5,5},异或结果为2,二进制表示为0010。异或得到的结果中倒数第二位为1,于是我们根据倒数第二位是不是为1分为两个子数组。第一个子数组{2,3,6,3,2},其中所有数字的倒数第二位为1;第二个子数组{4,5,5},其中所有数字的倒数第二位为0。接下来只要分别对这两个子数组求异或,就能找出第一个子数组中只出现一次的数字为6,第二个子数组中只出现一次的数字为4。
代码
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int size = data.size();
if(size <= 1){
return;
}
int result = data[0];
for(int i = 1;i < size;++i){
result ^= data[i];
}
int index = 0;
while((result != 0) && ((result & 1) == 0)){
result >>= 1;
++index;
}
result = (1 << index);
*num1 = 0;
*num2 = 0;
for(int i = 0;i < size;++i){
if((data[i] & result) > 0){
*num1 ^= data[i];
}
else{
*num2 ^= data[i];
}
}
}
};
int main(){
vector<int> num = {3,1,10,1,3,6,2,6};
int* num1 = new int(0);
int* num2 = new int(0);
Solution s;
s.FindNumsAppearOnce(num,num1,num2);
cout<<*num1<<" "<<*num2<<endl;
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
剑指 Offer 03. 数组中重复的数字原地置换,时间空间100%= i: # while 条件 是 符合排序后的条件还有个二分法的情况,暂时看不懂。
题目位置题解* 思路一:* 1、使用 map 存储每一个数字出现的次数,然后找到最大的* 思路二:* 1、数组中有一个数字出现的次数超过数组长度的一半 说明在这
《剑指Offer》 1. 赋值运算函数 2. 单例设计模式 3. 二维数组中查找目标值 4. 替换字符串中的空格 5. 从尾到头打印链表 6. 由前序和中序遍历重建二叉树 7. 用两个栈实现队列 8. 求旋转数组的最小数字 9. ...
这里的运用位运算的方法我属实是想不太来,这里用了一个32位的数组来计算每一个二进制位出现的次数,如果一个数字出现了3次,那么它的每一位肯定也是出现了3次的,所以
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
题目描述剑指 Offer 56 - I. 数组中数字出现的次数一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。示例 1:输出:[1,6] 或
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P00000007 输入描述: 题目保证输入的...
题目位置题解* 思路* 1、找到数组中元素最小的元素public int minArray(int[] numbers) {
例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。输入:[3,4,5,1,2]输出:1输入:[2,2,2,0,1]
例如 [1, 0, 1, 1, 1] 和 [1, 1, 1, 0, 1] ,在 left = 0, right = 4, mid = 2 时,无法判断 mid
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面剑指 Offer 21. 调整数组顺序使奇数位于偶数前面输入一个整数数组,实现一个函数来调整该数组中数字
剑指offer_Python版数组篇1.二维数组中的查找6.旋转数组中的最小值11.调整数组使奇数位于偶数前面19.顺时针打印矩阵28.数组中出现次数超过一半的数字30.连续子数组最大和32.把数组排出最小的数35.数组中的逆序对37....
剑指 Offer 57. 和为s的两个数字标签:数组、双指针、二分查找难度:简单题目大意给定一个升序数组 nums,以及一个目标整数 target。要求:在数组
Java 剑指offer(1) 找出数组中重复的数字.pdf
剑指 Offer 51. 数组中的逆序对(困难)在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。示例 1:输入: [7,5,6,
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。 解题思路参考:https://blog.csdn.net/flower_48237/article/details/104025402
数组中重复的数字 Y Y Y 剑指 Offer 04. 二维数组中的查找 Y Y Y 剑指 Offer 05. 替换空格 Y Y Y 剑指 Offer 10- I. 斐波那契数列 Y Y Y 剑指 Offer 10- II. 青蛙跳台阶问题 Y Y Y 剑指 Offer 11. 旋转数组的最小...
统计一个数字在排序数组中出现的次数。 解法一:分治法 # -*- coding:utf-8 -*- class Solution: def GetNumberOfK(self, data, k): left=0 right=len(data)-1 leftk=self.getleftK(data,k,left,right) rightk...