【转】http://zhedahht.blog.163.com/blog/static/2541117420071128950682/
题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
分析:这是一道很新颖的关于位运算的面试题。
首先我们考虑这个问题的一个简单版本:一个数组里除了一个数字之外,其他的数字都出现了两次。请写程序找出这个只出现一次的数字。
这个题目的突破口在哪里?题目为什么要强调有一个数字出现一次,其他的出现两次?我们想到了异或运算的性质:任何一个数字异或它自己都等于0。也就是说,如果我们从头到尾依次异或数组中的每一个数字,那么最终的结果刚好是那个只出现依次的数字,因为那些出现两次的数字全部在异或中抵消掉了。
有了上面简单问题的解决方案之后,我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中,包含一个只出现一次的数字,而其他数字都出现两次。如果能够这样拆分原数组,按照前面的办法就是分别求出这两个只出现一次的数字了。
我们还是从头到尾依次异或数组中的每一个数字,那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次,在异或中全部抵消掉了。由于这两个数字肯定不一样,那么这个异或结果肯定不为0,也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的位的位置,记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组,第一个子数组中每个数字的第N位都为1,而第二个子数组的每个数字的第N位都为0。
现在我们已经把原数组分成了两个子数组,每个子数组都包含一个只出现一次的数字,而其他数字都出现了两次。因此到此为止,所有的问题我们都已经解决。
基于上述思路,我们不难写出如下代码:
///////////////////////////////////////////////////////////////////////
// Find two numbers which only appear once in an array
// Input: data - an array contains two number appearing exactly once,
// while others appearing exactly twice
// length - the length of data
// Output: num1 - the first number appearing once in data
// num2 - the second number appearing once in data
///////////////////////////////////////////////////////////////////////
void FindNumsAppearOnce(int data[], int length, int &num1, int &num2)
{
if (length < 2)
return;
// get num1 ^ num2
int resultExclusiveOR = 0;
for (int i = 0; i < length; ++ i)
resultExclusiveOR ^= data[i];
// get index of the first bit, which is 1 in resultExclusiveOR
unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);
num1 = num2 = 0;
for (int j = 0; j < length; ++ j)
{
// divide the numbers in data into two groups,
// the indexOf1 bit of numbers in the first group is 1,
// while in the second group is 0
if(IsBit1(data[j], indexOf1))
num1 ^= data[j];
else
num2 ^= data[j];
}
}
///////////////////////////////////////////////////////////////////////
// Find the index of first bit which is 1 in num (assuming not 0)
///////////////////////////////////////////////////////////////////////
unsigned int FindFirstBitIs1(int num)
{
int indexBit = 0;
while (((num & 1) == 0) && (indexBit < 32))
{
num = num >> 1;
++ indexBit;
}
return indexBit;
}
///////////////////////////////////////////////////////////////////////
// Is the indexBit bit of num 1?
///////////////////////////////////////////////////////////////////////
bool IsBit1(int num, unsigned int indexBit)
{
num = num >> indexBit;
return (num & 1);
}
分享到:
相关推荐
一个数组,仅有两个数字出现一次,其他都是两次,找出这两个数字 思路: 思路:还是和当时的那道题目一样,用HashMap记录每个数字出现的次数,返回唯一两个get为0的数,加个flag分开即可 整合以上思路后,源码如下:...
一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请找出这两个只出现一次的数字。 # -*-coding:utf-8 -*- class Solution: def FindNumsAppearOnce(self, array): # 如果两个数相同,那么这两个数的...
给定两个整型数组,本题要求找出不是两者共有的元素。 输入格式: 输入分别在两行中给出两个整型数组,每行先给出正整数N(≤20),随后是N个整数,其间以空格分隔。 输出格式: 在一行中按照数字给出的...
已经两个已经排好序的数组,找出两个数组合起来的中间大的数字
给出一个递增数组array和由array中两个数的和n,求出这两个数? 求两个递增数组的最小距离,即在两个数组中各取一个数,使得这两个数的差最小? http://blog.csdn.net/ssuchange/article/details/17402991
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 实现代码如下: <?php function FindNumsAppearOnce($array) { // write code here // return list, 比如[a,...
主要介绍了C语言中找出数组中特定元素的算法解析,包括找出数组中两个只出现一次的数字的方法,需要的朋友可以参考下
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 分析 要解这题需要对异或操作有比较深的理解。 依次将数组中所有元素进行异或得到a,即num1和num2的异或。然后取a...
我们考虑如果每个数字都置出现一次,那么此时是最完美的,每一个下标i对应元素numbers[i],也就是说我们对于数组中的每个元素numbers[i]都把它放在自己应该在的位置上numbers[numbers[i]]上, 如果我们发现有两个元素...
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 ...
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。 解题思路:要求时间复杂度为o(n),空间复杂度O(1),如果没有这些要求,...
主要介绍了JS取出两个数组中的不同或相同元素,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
5.19 已知数组A包含15个互不相等的整数,试编写一程序,把既在A中又在B中出现的整数存在于数组中C中。 5.20 设在A,B和C单元中存放着三个数,若三个数都不是0,则求出三树之和并存放于D单元中;其中有一个数为0,则把...
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。 两种方式: 1...
1、从弹框中,分两次输入两个数字,分别保存在 a 和 b中 2、如果 a 大于 b的话 ,则交换两个数字的位置 使用 短路&&,扩展赋值运算符,位运算 4、条件运算符(三目运算) 单目(一元)运算符 :++,--,! 双目(二元)...
# 有序数组的平方 ...# 方法比较多, 比如先找出最中心的数字后转换成两个数组进行归并运算, 但是双指针方法是最简单的 # 截止条件定在为正负分界线上, 一旦达到表示其中一个数字遍历完毕, 剩下的直接进行追加即可
首先看到这题,我们需要找到那个唯一的只出现一次的数字,而其他的数字都是只出现了两次,那么我们如果一个一个的去数组里找是否有重复的,这样时间复杂度会很大,所以我们要想如何更加简单的找出唯一的只出现一次的...
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。 示例 1: 输入:nums = [4,1,4,6] 输出:[1,6] 或 [6,1] 示例 2: ...
下面小编就为大家分享一篇java 判断一个数组中的数值是否连续相邻的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 思路...