异或运算面试题——一个数组中有一种数出现K次，其它数都出现了M次，M＞1且K＜M， 找到出现了K次的数，并要求额外空间复杂度为O(1)，时间复杂度为O(N)

异或运算面试题——一个数组中有一种数出现K次，其它数都出现了M次，M＞1且K＜M， 找到出现了K次的数，并要求额外空间复杂度为O(1)，时间复杂度为O(N) 题目：一个数组中有一种数出现K次，其它数都出现了M次，M>1且Kpackage com.harrison.class01; import java.util.HashMap; import java.util.HashSet; public class Code12_KM { public static int onlyKTimes(int[] arr,int k,int m){ int[] t=new int[32]; for(int num:arr){ for(int i=0; i<=31; i++){ t[i]+=(num>>i)&1; } } int ans=0; for(int i=0; i<32; i++){ if((t[i]%m)!=0){// 在第i位上有1 ans |= (1< map=new HashMap<>(); for(int num:arr){ if(map.containsKey(num)){ map.put(num,map.get(num)+1); }else{ map.put(num,1); } } for(int num:map.keySet()){ if(map.get(num)==k){ return num; } } return -1; } public static int[] generateRandomArray(int maxKinds,int range,int k,int m){ // 出现了K次的这种数 int kTimesNum=randomNumber(range); // 数的种类 numKinds >=2 int numKinds=(int)(Math.random()*maxKinds)+2; // 数组长度： 1*k + (numKinds-1)*m int[] arr=new int[k+(numKinds-1)*m]; int index=0; for( ; index set=new HashSet<>(); set.add(kTimesNum); while(numKinds!=0){ int curNum=0; do{ curNum=randomNumber(range); }while(set.contains(curNum)); set.add(curNum); numKinds--; for(int i=0; i

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5709505.html