题目：一个数组中有一种数出现K次，其它数都出现了M次，M>1且K<M，找到出现了K次的数，并要求额外空间复杂度为O(1)，时间复杂度为O(N)

package com.harrison.class01;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author Harrison
 * @create 2022-01-22-16:44
 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
 */

/*
题目：一个数组中有一种数出现K次，其它数都出现了M次，M>1且K<M，
找到出现了K次的数，并要求额外空间复杂度为O(1)，时间复杂度为O(N)
 */
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<<i);// 1左移i个位置
            }
        }
        return ans;
    }

    public static int test(int[] arr,int k,int m){
        HashMap<Integer,Integer> 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<k; index++){
            arr[index]=kTimesNum;
        }
        // 还剩多少种数要填
        numKinds--;
        HashSet<Integer> 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<m; i++){
                arr[index++]=curNum;
            }
        }
        // arr 已经填好了，接下来打乱数组的顺序
        for(int i=0; i<arr.length; i++){
            // i位置的数 随机和 j位置的数 做交换
            int j=(int)(Math.random()*arr.length);// 0~N-1
            int tmp=arr[i];
            arr[i]=arr[j];
            arr[j]=tmp;
        }
        return arr;
    }

    // return [-range,+range]中的一个数
    public static int randomNumber(int range){
        return (int)(Math.random()*(range)+1)-(int)(Math.random()*(range)+1);
    }

    public static void main(String[] args) {
        int maxKinds=10;
        int range=200;
        int testTimes=100000;
        int max=9;
        System.out.println("test begin");
        for(int i=0; i<testTimes; i++){
            int a=(int)(Math.random()*max)+1;// 1~9
            int b=(int)(Math.random()*max)+1;// 1~9
            int k=Math.min(a,b);
            int m=Math.max(a,b);
            if(a==b){
                m++;
            }
            int[] arr=generateRandomArray(maxKinds,range,k,m);
            int ans1=onlyKTimes(arr,k,m);
            int ans2=test(arr,k,m);
            if(ans1!=ans2){
                System.out.println("oops");
            }
        }
        System.out.println("test finish");
    }
}