【3】数组中只出现一次的数字

题目:输入一个整型数组,数组里除了两个数出现一次之外,其它所有数字出现的次数都是2次,求这两个数字。要求时间复杂度为O(n),空间复杂度为O(1)

1 题目要求时间复杂度为O(n)并且空间复杂度为O(1)。这个时候朴素的方法利用数字来记录出现次数的方案都是不行的。

2 根据题目的特点,只有两个数出现一次,其它的所有数据都是出现2次。如果这两个数是a和b,那么对这个数组异或的结果就是a^b。现在我们就是要考虑怎么把数组分成两部分,一部分含有a,一部分含有b,则每部分异或的结果即为两个数a和b的值

3 因为a肯定不等于b,所以a^b的结果肯定不会等于0,那么我们可以就去这个异或结果中最右边的第一个1的位置,根据这个位置来划分这个数组,这个位置是1的位一部分,不是1的分为一部分。

4 例如数组{2,4,3,6,3,2,5,5},数组异或的结果为2,二进制位0010最右边1的位置为第二位。则我们把数组分成两部分{2,3,6,3,2}中每个数的二进制最右边第二位为1,剩下一部分{4,5,5}中每个数二进制最右边第二位为0。

5 求出两部分之后我们就可以直接对每部分求异或即可求出两个数的值

//找到两个只出现一次的数
void FindNumAppearOnce(int *arrNum, int n){
	//空指针和个数小于2都是不合法的数据
	if(arrNum == NULL || n < 2){
	    return;
	}
	//先求出总的异或的值
	int sum = 0;
	for(int i = 0; i < n; i++){
	    sum ^= arrNum[i];
	}
	//找到sum的右边第一个1的位置
	int pos = 0;
	while((sum & 1) != 1 && (pos <= 32)){
	    pos++;
		sum >>= 1;
	}
	//没有找出第一个1的位置
	if((pos == 0) || (pos > 32)){
	    return;
	}
	//定义两个数为
	int numOne = 0;
	int numTwo = 0;
	//枚举求出
	int num = 1<<pos;
	cout<<num<<endl;
	for(int i = 0; i < n; i++){
		if((arrNum[i]&num) != 0){
		    numOne ^= arrNum[i];
		}
		else{
		    numTwo ^= arrNum[i];
		}
	}
	cout<<numOne<<" "<<numTwo<<endl;
}
时间: 2024-10-30 11:43:32

【3】数组中只出现一次的数字的相关文章

[剑指Offer]40.数组中只出现一次的数字

题目 一个整型数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 思路 我们直到异或的性质: 任何一个数字异或他自己都等于0. 所以说我们如果从头到尾依次异或每一个数字,那么最终的结果刚好只出现一次的数字,因为成对出现的两次的数字全部在异或中抵消了. 这道题中有两个数字只出现一次.这样的话我们得到的结果就是这两个数字的异或结果.因此我们想办法把原数组分成两个子数组,使得每个子数组包含一个只出现一次的数字.这样我们就可以对这两个子数组分别异或,就能得到两个只出现一

如何数组中只出现一次的数字

题目描述 一个整型数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 输入 每个测试案例包括两行 第一行包含一个整数n,表示数组大小.2<=n <= 10^6. 第二行包含n个整数,表示数组元素,元素均为int. 输出 对应每个测试案例,输出数组中只出现一次的两个数.输出的数字从小到大的顺序. 样例输入: 8 2 4 3 6 3 2 5 5 样例输出: 4 6 思路:上篇博文中已经了解到异或去重的原理,而且知道如果只有一个只出现一次的数字的求法,但这里是有两个

求数组中只出现一次的数字的算法

题目: 一个整型数组里除了两个数字以外, 其他的数字都出现了两次. 请写程序找出这两个只出现一次的数字. 如果从头到尾依次异或数组中的每一个数字, 那么最终的结果刚好是那个只出现一次的数字. 根据结果数组二进制某一位为1, 以此分组, 为1的一组, 为0的一组, 再重新进行异或. 最后得出两个结果. 时间复杂度O(n). 代码: /* * main.cpp * * Created on: 2014.6.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*

剑指offer系列之三十九:数组中只出现一次的数字

题目描述 一个整型数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 先考虑只有只有一个数字出现一次的情况,因为其他数字只出现了两次,所以对这两个数字进行异或运算的时候,其结果是0,那么那个只出现一次的数字进行异或运算的时候,其结果必然不是0,所以可以利用这点找出那个只出现一次的数字.现在考虑有两个数字出现一次的情况,仍然借鉴上面的思路,因为只出现一次的那个数字的异或结果不是0,遍历整个数组进行异或运算的结果也肯定不是0,现在可以对该数右边第一个是1的位的位置作

《剑指offer》-数组中只出现一次的数字

/* 一个整型数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 思路: 如果是只有一个数字出现一次,那么所有数字做异或就得到结果: 现在有两个数字x,y分别出现一次,其他数字出现两次,那么所有数字异或的结果是result = x^y x^y肯定不等于0,那么找其二进制表示中不等于0的一个位,比如从右到左第一个位置好了,那么用这个位置能区分开来这两个数字,以及其他的数字,每两个一样的数字都处于同一边. */ class Solution { public: vo

求数组中只出现一次的数字(算法)

首先,我们先考虑简单的情况下,就是只有一个出现一次的数字,其余数字都出现2次,这样我们可以采用一种很巧妙的方法:"异或". void findNumAppearOnce(int date[],int length,int &num) { if(length<2) return; num=0; for(int i=0;i<length;i++) { num ^=date[i]; } } 然后,我们考虑有两个出现一次的数字的情况.同理,我们依然采用上面的方法,由于两个出

怎样在Excel中只显示大于10的数字?

  今天我们来学习一下Excel中一个小技巧,在Excel设置只显示大雨10的数字,你知道如何操作码?如果不懂就一起来学习一下操作技巧吧. 怎样在Excel中只显示大于10的数字? 如下图所示,B列是数字,字母混杂的内容.要求只显示大于10的数字,其他的都隐藏起来. 操作步骤: 选取区域 - ctrl+数字1打开单元格设置窗口 - 数字 - 自定义 - 在右边文本框中输入自定义代码 :[>10]G/通用格式; 注意:红色的要全部输入,包括最后的英文状态引号(;) 设置完成的效果如下图所示. 这样

用PHP的正则表达式匹配字符串中只出现两次的数字

问题描述 用PHP的正则表达式匹配字符串中只出现两次的数字 列如:$user = ""aaa128ddd224545frgrg22greb5sdb44vd12vf56"";把只出现两次的数字找出来224456 解决方案 $user = ""aaa128ddd224545frgrg22greb5sdb44vd12vf56"";$zzd='/((d)\2)/is';preg_match_all($zzd$user$adsx);pr

经典算法(12) 数组中只出现1次的两个数字(百度面试题)

首先来看题目要求: 在一个数组中除两个数字只出现1次外,其它数字都出现了2次, 要求尽快找 出这两个数字. 考虑下这个题目的简化版--数组中除一个数字只出现1次外,其它数字都成对出现 ,要求尽快找出这个数字.这个题目在之前的<位操作基础篇之位操作全面总结>中的"位操作趣味应用" 中就已经给出解答了.根据异或运算的特点,直接异或一次就可以找出这个数字. 现在数组中有两个 数字只出现1次,直接异或一次只能得到这两个数字的异或结果,但光从这个结果肯定无法得到这个两个数字 .因此我