栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

算法学习一:给定一个数组,其中一个数出现了奇数次,其他出现了偶数次,求奇数次的数

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

算法学习一:给定一个数组,其中一个数出现了奇数次,其他出现了偶数次,求奇数次的数

算法学习一:给定一个数组,其中一个数出现了奇数次,其他出现了偶数次,求奇数次的数

解答该题需要运用到异或(^)的操作。具体代码如下(java代码为例):

public static void main(String[] args) {

		//给定一个int型数组:里面只出现奇数次的数为 4 ,其他均出现了偶数次
		int[] arrayInt = new int[]{1,1,2,2,3,3,4,5,5,6,6};
		
		//解答该题,非常简单。
		//什么是异或? 相同为0,不同为1,定义一个默认值,挨个与数组每个值去进行异或操作。那么,
		//自然,出现偶数次的数,异或后全部是0,到最后得到的结果就是出现奇数的那个数字
		int eor = 0;
		for (int i: arrayInt
			 ) {
			eor  ^= i;
		}
		System.out.println(eor  );
	}


输出结果为:4

扩展一:给定一个数组,有2个数出现了奇数次,其他出现了偶数次,求奇数次的2个数分别是多少?
解答该题同样用到异或
具体解法如下(java为例):

public static void main(String[] args) {
		//给定一个int型数组:里面只出现奇数次的数为 4和 185 ,其他均出现了偶数次
		int[] arrayInt = new int[]{1,1,2,2,3,3,4,5,5,6,6,185,199,199,75,75};
		int eor = 0;
		for (int i: arrayInt
		) {
			eor  ^= i;
		}
		//eor = a^b
		//eor !=0,因为有俩个出现奇数次的数,所以eor异或后,肯定不为0
		//eor必然有一个位置上是1
		int rightOne = eor & (~eor + 1);//提取出最右的1(**把某个不为0的数,最右侧的1提取出来**)
		int onlyOne = 0;
		for(int cur : arrayInt){
			if((cur & rightOne) == 1){
				onlyOne ^= cur;
			}
		}
		System.out.println(onlyOne+" "+(eor ^ onlyOne));
	}

输出结果为 185 4

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/532281.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号