首页 > 代码库 > 数组中只出现一次的数字
数组中只出现一次的数字
- 题目
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)
- 思路
根据【异或】原理，任何一个数与自身异或的结果都为0以及任何数与0异或的结果都是其本身，所以本题可以将数组的所有的元素异或，得到结果即是只出现一次的两个元素异或结果。然后在异或结果中找出第一比特位为“1”的位置index，然后判断数组的中元素的index为是否为1，分为两组
- 代码实现
public class Algorithm { /**获得数组source中只出现一次两个的元素*/ public static int [] getOneTimeNuber(int []source) { int [] result = new int[]{0,0}; // 结果 int resultOR = 0; // 异或结果 for(int i = 0;i < source.length; ++i) { resultOR ^= source[i]; } /**找出异或结果的第一个比特位为1的位置*/ int pos = findFirstBitIs1(resultOR); /**根据第一个比特位为1将元素分为两组,即第pos位为0与第pos为1的两组*/ for(int i = 0;i < source.length; ++i) { if(isBit1(source[i], pos)) { /**1*/ result[0] ^= source[i]; } else { result[1] ^= source[i]; } } return result; } /**找出第一个比特位为1的位置*/ public static int findFirstBitIs1(int num) { int index = 1; while((num & 1) == 0 && index < 32) { num = num >> 1; // 右移1位 ++index; } return index; } /**判断元素第pos位是否为1*/ public static boolean isBit1(int num, int pos) { num = num >> pos - 1; // 右移pos - 1 位 if((num & 1) == 1) return true; return false; } public static void main(String []args) { int [] array = new int[]{1,2,2,3,3,6}; int [] result = Algorithm.getOneTimeNuber(array); System.out.println(result[0] + "\t" + result[1]); }}
数组中只出现一次的数字
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。