#include <iostream>
using namespace std;
/**
* 题目:有N+2个数,N个数出现了偶数次,2个数出现了奇数次(这两个数不相等),
* 问用O(1)的空间复杂度,找出这两个数,不需要知道具体位置,只需要知道这两个值。
* */
/**
* 假设不相同的两个数字是x和y。他们的异或结果一定不是0,假设为xor。
* xor的最低位1就是他们不相同的其中一位,比如是第lowbit位。
* 那么x的lowbit位为1,y的lowbit位为0,或者相反。
*
* 我们将所有a[]中第lowbit位为1的所有元素异或起来,这些元素中一定有x没有y
* 其他出现两次的异或都为0抵消了。所以最后结果就是xor ^ x = y这样就求出y了
* x = xor ^ y
*/
void findTwoNumber(int a[], int n){
int xor = a[0];
for(int i=1;i<n;i++)
xor = xor^a[i];
int lowbit = xor & ~(xor-1); //利用这个操作可以进保留最低位1,其他全部清零
int x = 0;
for(int j=0;j<n;j++){
if(a[j] & lowbit){ //查看lowbit位是否是1
x = x^a[j];
}
}
int y = xor ^ x;
cout<<x<<endl;
cout<<y<<endl;
}
int main(){
int a[] = {1,4,3,1,5,2,2,4,7,3};
findTwoNumber(a, 10);
return 0;
}
分享到:
相关推荐
请找出这两个只出现一次的数字。 # -*-coding:utf-8 -*- class Solution: def FindNumsAppearOnce(self, array): # 如果两个数相同,那么这两个数的异或操作就等于0 if len(array) > 1 count += 1 mask = 1 <...
/*找出一个数组中的两个唯一出现过一次的数字,其他数组都出现了两次。 思路:还是和当时的那道题目一样,用HashMap记录每个数字出现的次数,返回唯一两个get为0的数,加个flag分开即可*/ public class item38 { ...
网上那种找出两个数组重复元素的代码复杂度较高,这个比较简单,一次循环搞定
给定一个非空整数数组,除了某个元素只出现一次之外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明:算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗? 链接:...
题目描述:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗? ...
请写程序找出这两个只出现一次的数字。 分析 要解这题需要对异或操作有比较深的理解。 依次将数组中所有元素进行异或得到a,即num1和num2的异或。然后取a中二进制为1的一个位置,找到原数组中所有该位为1的数字进行...
首先看到这题,我们需要找到那个唯一的只出现一次的数字,而其他的数字都是只出现了两次,那么我们如果一个一个的去数组里找是否有重复的,这样时间复杂度会很大,所以我们要想如何更加简单的找出唯一的只出现一次的...
【输入形式】 从标准输入读取输入。第一行只有一个数字N(1≤N≤10000),代表整数的个数。以后的N行每行有一个整数。 【输出形式】 向标准输出打印出现次数...输入6个整数,其中出现次数最多的是0,共出现两次。
32位无符号整数的范围是0 ~ 4 294 967 295 现在有40亿个无符号整数,可以使用最多1GB的内存,找出所有出现了两次的数。 补充问题: 可以使用最多10MB的内存,怎么找到40亿个整数的中位数? 原问题: 可以用 bit map ...
(1)设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数,设计一个算法复杂度为O(logn)的分治算法,找出X和Y中2n个数中的中位数。(中位数:个数为奇数:中间位置上的数;个数为偶数,中间两个数的...
请写程序找出这两个只出现一次的数字。 实现代码如下: <?php function FindNumsAppearOnce($array) { // write code here // return list, 比如[a,b],其中ab是出现一次的两个数字 $count = array_count_...
用matlab如何求出一个数组中最接近某个数的两五个数,带有测试图片,要求大于五个只需要按程序一次添加相应的代码!
这个程序首先定义了两个辅助函数 countDigits 和 isNarcissistic,用于计算数字的位数和判断一个数是否为水仙花数。然后定义了 findNarcissisticNumbers 函数来找出指定范围内的水仙花数。最后,在 main 函数中,...
题目:输入两个正整数m和n,求其最大公约数。 /**提示:在循环中,只要除数不等于0,用较大数除以较小的数,将小的一个数作为下一轮循环的大数,取得的...a说他不和x比,c说他不和x,z比,请编程序找出三队赛手的名单。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。 解题思路:要求时间复杂度为o(n),空间复杂度O(1),如果没有这些要求,这题很简单,直接用set去重,遍历数字用字典统计个数,输出个数...
5.2 编写程序,从键盘接收一个小写字母,然后找出它的前导字符和后续字符,再按顺序输出 5.3 将AX寄存器中的16位数分成4组,每组4位,然后把这四组数分别放在AL、BL、CL、DL中。 5.4 试编写一程序,要求比较两个字符...
第三步:从第一步和第二步求得的质因数分解式中找出所有的公因数(如果p是一个公因数,而且在m和n的质因数分解式中分别出现过pm和pn次,那么应该将p重复min{pm,pn}次)。 第四步:将第三步中找到的质因数相乘,其...
给定一个整数数组,返回两个数字的索引,使它们相加为特定目标。 您可以假设每个输入都只有一个解决方案,并且您不能两次使用相同的元素。 例子: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums...
就像: 8 1 3 6 2 从最左边接下去数8个数字: 1 3 6 2 8 1 3 6 所以下一个数字是6重复这样做 (这次从“6”开始数6个数字) 并且你会停止在一个新的数字上: 2 8 1 3 6 2, 也就是2再这样做 (这次数两个): 8 1再一次 (这次...
给出你设计的求解下面问题算法的伪代码并分析复杂性: 设B={b1,b2,…,bn} 和 W={w1,w2,…,wn}为平面上黑点和白点的两个集合。...设计一贪心算法,找出黑白点之间的最大匹配数目。算法的复杂性要尽量接近nlgn.