一个整数数组里面,除了两个数之外,其他的数字都出现了两次,写一个程序找出这两个数,要求算法的时间复杂度为O(n).
n为数组的长度。
程序代码如下:
//取二进制中首个为1的位置 int findFirstOne(int value) { int pos = 0; while ((value&1) != 1) { value = value>>1; pos++; } return pos; } //测试某位置是否为1 char testBit(int value, int pos) { return ((value>>pos)&1); } int findNums(int date[], int length, int *num1, int *num2) { if (length < 2) { return -1; } int ansXor=0; int i = 0; int pos = 0; for (i=0; i<length; i++) { ansXor ^= date[i]; //异或 } pos = findFirstOne(ansXor); *num1 = *num2 = 0; for(i=0; i<length; i++) { if (testBit(date[i], pos)) { *num1 ^= date[i]; } else { *num2 ^= date[i]; } } return 0; }
1、首 先 第一次遍历整个数组,找出不同的那两个数的异或后的结果,见下面 这段代码 .
for (i=0; i<length; i++)
{
ansXor ^= date[i]; //异或
}
2、找到异或结果中ansXor中用移位的方式找到第一个二进制数中为1的位置,这个很关键,找到这个位置后,说明在该位置上,这两个不同的数中,一个为0,一个为1,这个应该可以理解对吧?
//取二进制中首个为1的位置 int findFirstOne(int value) { int pos = 0; while ((value&1) != 1) { value = value>>1; pos++; } return pos; }
我们把这个位置记为pos
3、然后再遍历一次数组,把这个数组分成两个子数组,pos位上为1的,和pos位上为0的
for(i=0; i<length; i++) { if (testBit(date[i], pos)) { *num1 ^= date[i]; } else { *num2 ^= date[i]; } }
这里借助了异或的原理,pos位置上为1的其它成双成对的数肯定也是为1的,同理,pos位上为0的时也一样。
上面程序思路是我参考别人思路编写的代码,欢迎大家提出好的思路,一起学习一起进步!
相关推荐
【输入形式】 从标准输入读取输入。第一行只有一个数字N(1≤N≤10000),代表整数的个数。以后的N行每行有一个整数。 【输出形式】 向标准输出打印出现次数...输入6个整数,其中出现次数最多的是0,共出现两次。
5.2 编写程序,从键盘接收一个小写字母,然后找出它的前导字符和后续字符,再按顺序输出 5.3 将AX寄存器中的16位数分成4组,每组4位,然后把这四组数分别放在AL、BL、CL、DL中。 5.4 试编写一程序,要求比较两个字符...
给定一个整数数组,返回两个数字的索引,使它们相加为特定目标。 您可以假设每个输入都只有一个解决方案,并且您不能两次使用相同的元素。 例子: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums...
给定一个非空整数数组,除了某个元素只出现一次之外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明:算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗? 链接:...
循环数是那些不包括0且没有重复数字的整数(比如81362)并且还应同时具有一个有趣的性质, 就像这个例子:如果你从最左边的数字开始(在这个例子中是8)向右数最左边这个数(如果数到了最右边就回到最左边),你会停止在另一...
8.7写一函数,输入一个4位数字,要求输出这4个数字字符,但每两个数字之间有一个空格。如输入1990,应输出”1 9 9 0”。 52 8.8编写一函数,有实参传来一个字符串,统计此字符串中字母,数字,空格和其它字符的个数...
首先看到这题,我们需要找到那个唯一的只出现一次的数字,而其他的数字都是只出现了两次,那么我们如果一个一个的去数组里找是否有重复的,这样时间复杂度会很大,所以我们要想如何更加简单的找出唯一的只出现一次的...
题目描述:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗? ...
第三步:从第一步和第二步求得的质因数分解式中找出所有的公因数(如果p是一个公因数,而且在m和n的质因数分解式中分别出现过pm和pn次,那么应该将p重复min{pm,pn}次)。 第四步:将第三步中找到的质因数相乘,其...
32位无符号整数的范围是0 ~ 4 294 967 295 现在有40亿个无符号整数,可以使用最多1GB的内存,找出所有出现了两次的数。 补充问题: 可以使用最多10MB的内存,怎么找到40亿个整数的中位数? 原问题: 可以用 bit map ...
中的一个数字丢失,并且一个数字在数组中出现了两次。 找出这两个数字。 给定一个整数数组 nums,找出其总和最大的连续子数组(至少包含一个数字)并返回其总和。 给定一组区间,合并所有重叠的区间。 输入:区间 = ...
(12)编写程序验证以下说法:输入一个4位数,该数个、十、百、千位上的数互不相等,由个、十、百、千位上的数组成一个最大数和一个最小数,最大数-最小数,构成一个新的4位数。反复以上运算,使其最终结果为:6174...
题目:输入两个正整数m和n,求其最大公约数。 /**提示:在循环中,只要除数不等于0,用较大数除以较小的数,将小的一个数作为下一轮循环的大数,取得的余数作为下一轮循环的较小的数, 如此循环直到较小的数的值为0...
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 示例: 给定 nums =...
40027 从高位开始逐位输出一个整数的各位数字(选作) 39 40052 判断素数 40 40053 逆序输出整数 41 40054 输出斐波那契序列 42 第7周(M7) 42 50002 使用函数判断数的符号 42 50003 使用函数求奇数和 43 50005 使用...
1.程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 【程序3】 题目:打印出所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和...
0086 用回溯法找出n个自然数中取r个数的所有组合 58 0087 0~N位数的任意组合 59 0088 在数组中快速查找近似值 60 0089 实现直接插入法排序 61 第4章 函数应用 63 4.1 字符串处理函数 64 0090 使用...
假设商店货品价格(R) 都不大于100元(且为整数),若顾客付款(P)在100元内,现有一个程序能在每位顾客付款后给出找零钱的最佳组合(找给顾客货币张数最少)。 假定此商店的货币面值只包括:50元(M50)、10元(M10)、 5...
1.程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 【程序3】 题目:打印出所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和...
1.6.3. 输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数 位于数组的后半部分 ...........................................................130 1.6.4. 给定链表的头指针和一个...