`

给你n个数,其中有且仅有三个数出现了奇数次,其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那三个数(代码)。

J# 
阅读更多

public class FindOdd {
	public static void main(String args[]){
		for(int i=0;i<10000;i++){
			if(!test()){
				System.out.println("Error Occurs: "+i);
				break;
			}
		}
		System.out.println("Well Job! All Pass.");
	}
	
	public static boolean test(){
		int num = (int)(Math.random()*102400)*2;
		int multi = 500;
		int[] test = new int[num+3];
		for(int i=0; i<num;i+=2){
			test[i] = (int)(Math.random()*num*multi);
			test[i+1] = test[i];
		}
		test[num] = (int)(Math.random()*num*multi);
		test[num+1] = (int)(Math.random()*num*multi);
		while(test[num+1]==test[num])
			test[num+1] = (int)(Math.random()*num*multi);
		test[num+2] = (int)(Math.random()*num*multi);
		while(test[num+2]==test[num]||test[num+2]==test[num+1])
			test[num+2] = (int)(Math.random()*num*multi);

		System.out.println("test["+num+"]: " + test[num]);
		System.out.println("test["+(num + 1)+"]: " + test[num+1]);
		System.out.println("test["+(num + 2)+"]: " + test[num+2]);
		
		int[] result= findThree(test);
		
		System.out.println("result[0]: " + result[0]);
		System.out.println("result[1]: " + result[1]);
		System.out.println("result[2]: " + result[2]);
		
		return (result[0]==test[num]&&result[1]==test[num+1]&&result[2]==test[num+2])
			||(result[0]==test[num]&&result[2]==test[num+1]&&result[1]==test[num+2])
			||(result[1]==test[num]&&result[0]==test[num+1]&&result[2]==test[num+2])
			||(result[1]==test[num]&&result[2]==test[num+1]&&result[0]==test[num+2])
			||(result[2]==test[num]&&result[0]==test[num+1]&&result[1]==test[num+2])
			||(result[2]==test[num]&&result[1]==test[num+1]&&result[0]==test[num+2]);
	}
	
	public static int[] findThree(int[] list){
		int[] result = new int[3];
		int nums1=0,nums2=0,result1=0,result2=0;
		int exploc = 1;
		int temp;
		while(true){
			nums1=0;
			nums2=0;
			result1=0;
			result2=0;
			
			for(int i=0;i<list.length;i++){
				if((list[i]&exploc)==exploc){
					//the k-th bit is 1
					nums1++;
					result1^=list[i];
				} else{
					//the k-th bit is 0
					nums2++;
					result2^=list[i];
					
				}
			}
			if((nums1&1)==1){
				temp = nums2;
				nums2 = nums1;
				nums1 = temp;
				temp = result2;
				result2 = result1;
				result1 = temp;
			} 
			//nums1 are even
			
			if(result1==0){
				//these three number are in zeros
			}else{
				//there are only one in zeros, so
				result[0] = result2;
				
				int j=0;
				int exp = 1;
				while(true){
					if((result1&exp)==exp)
						break;
					j++;
					exp<<=1;
				}
				
				result1 = 0;
				result2 = 0;
				for(int i=0;i<list.length;i++){
					if((list[i]&exp)==exp){
						//the oneloc-th bit is 1
						result1^=list[i];
					} else{
						//the oneloc-th bit is 0
						result2^=list[i];
					}
				}
				if((result[0]&exp)==exp){
					result[1] = result1^result[0];
					result[2] = result2;
				}else{
					result[1] = result1;
					result[2] = result2^result[0];
				}
				break;
			}
			
			exploc<<=1;
		}
		
		return result;
	}
}
分享到:
评论
1 楼 lvbolvtian 2012-08-13  
楼主最好贴上思路先  

相关推荐

    考研线性代数知识点全面总结借鉴.pdf

    奇排列在变为标准排列时,需要进行奇数次对换,而偶排列则需要偶数次。 ### 行列式性质 行列式具有以下性质: 1. 转置行列式与原行列式相等。 2. 互换两行(列)行列式变号。 3. 若两行(列)相等或成比例,行列式...

    高等代数简明教程1.3线性方程组.pdf

    但如果齐次线性方程组的系数矩阵A的列向量线性无关,则该方程组有且仅有一个解,即零解。如果系数矩阵的列向量线性相关,那么方程组有无穷多个非零解。齐次线性方程组有非零解的充分必要条件是系数矩阵A的秩小于未知...

    线性代数练习册-答案.doc

    逆序数是排列中任意两个数字位置交换的次数,偶数个逆序数对应偶排列,奇数个对应奇排列。 3. **行列式的性质与展开**:行列式的性质包括线性性、反对称性、范德蒙德恒等式等。文档中的练习题(1)至(4)展示了...

    线性代数第一章习题集.doc

    - **行列式的展开定理**:行列式可以通过任意行(列)展开,展开项的符号取决于行(列)的交换次数,偶数次交换为正,奇数次交换为负。 2. **Laplace展开定理**: - 在行列式中选择行或列,由这些行或列的元素...

    线性代数课件第1章行列式PPT学习教案.pptx

    线性代数是数学的一个重要分支,主要研究向量、矩阵和线性变换等概念。在第一章中,我们聚焦于行列式,它是线性代数的基础之一,具有广泛的应用,如在解决线性方程组、计算矩阵的逆以及确定矩阵是否可逆等问题。 ...

    07-08代数试卷模板A.doc

    - 实对称矩阵是正定的,当且仅当它的所有特征值都是正的。 10. **行列式计算**: - 行列式的计算是线性代数的基础,通常涉及拉普拉斯展开或 cofactor 扩展法。 11. **矩阵的逆**: - 求解方阵的逆矩阵,这需要...

    07-08代数A.doc

    一个实对称矩阵是正定的,当且仅当所有的特征值都是正的。因此,正定矩阵的所有特征值必须是正的。 9. **行列式计算**:这是一个具体的计算任务,要求计算给定的行列式,这通常涉及到行列式的展开、约简或者利用...

    江西省上饶县高二数学上学期第二次月考试题(理零)-7页.pdf

    9. **组合问题**:涉及到组合计数和排列组合,要计算总分为8时,仅有两个红球相邻的排法数。 10. **等比数列性质**:由数列的性质,可以得出等比数列的通项公式,从而求解m的值。 11. **循环结构和算法**:程序...

    安徽省宣城市郎溪县郎溪中学2015-2016学年高二数学下学期第一次月考试题文(无答案).doc

    7. **反证法**:反证法证明“自然数a, b, c中恰有一个偶数”时,正确的假设是a, b, c全部是奇数或至少有两个偶数,因为这与结论“恰有一个偶数”矛盾。 8. **空间几何**:类比平面内的性质,可以推导空间中的类似...

    吉大 各种基本ACM必备算法基础

    若仅有两个节点的度数为奇数,则存在欧拉路径。可以通过遍历的方式找到欧拉路径。 ##### DIJKSTRA数组实现O(N^2) Dijkstra算法是一种用于解决单源最短路径问题的经典算法。当使用数组而不是优先队列实现时,其时间...

    2000普及组初赛试题

    - **解析**:如果两端都是相同的小鸟,则整个线段可以被分为多个小段,其中相邻的鸟相同和不同的段交替出现,故不同小鸟的线段一定是偶数个。 - **答案**:B.偶数 #### 20. 程序输出 - **题目**:请仔细阅读下列...

    SPWM技术详解

    SPWM波形的生成主要有三种方法:计算法、调制法和跟踪法。 1. **计算法**:这种方法是根据面积等效原理,通过数字计算来确定每个脉冲的宽度和间隔,从而生成PWM波形。虽然理论上可行,但在实际应用中这种方法过于...

    湖北省荆门市龙泉中学2013届高中三年级上学期10月月考数学文试题.doc

    (2)设h(x)是定义在R上的偶函数,对任意的x,都有h(x+h(x))=2+h(x),且当x∈[0,1]时,h(x)=x,若关于x的方程h(x)+a=2x在区间[0,2]恰有三个不同实根,则实数a的取值范围是”,需要用到函数的对称性和最值的求解方法。...

    数学建模-第十章 图论模型.zip

    4. **树**:树是一种特殊的图,没有环路,且任意两个顶点间有且仅有一条路径。树的度数性质是所有顶点的度之和等于边数的两倍减去顶点数。 5. **欧拉路径与哈密顿回路**:欧拉路径是从一个顶点出发,经过每条边一次...

    广东省揭阳市普宁市英才侨中2015_2016学年高二数学上学期第三次月考试卷理含解析

    等比数列{an}中,各项都是正数,根据等比数列的性质,我们知道an=a1*q^(n-1),其中a1是首项,q是公比。题目中提到a1a2a3=5和a7a8a9=10,可以利用指数运算的性质得出: a1*a1*q*a1*q^2=5 (因为a2=a1*q, a3=a1*q^2) a7...

    山东省乐陵市第一中学2015届高三数学 第8周 周末反馈

    中的问题与基本不等式有关,即a^2+b^2≥2ab,当且仅当a=b时等号成立,用以求解ab的取值范围。 8. **几何比例问题**:8.中通过向量的线性运算,探讨了三角形面积的比例关系,需要用到向量平行四边形法则及三角形面积...

Global site tag (gtag.js) - Google Analytics