有一个数组arr，其中只有一种数出现了K次，其余所有的数都都出现了M次。

package class02;

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

/**
 * 有一个数组arr，其中只有一种数出现了K次，其余所有的数都都出现了M次。
 * K < M，M > 1。
 */
public class Code03_KM {
    public static int test(int[] arr, int k, int m) {
        Map<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);
            }
        }
        int ans = 0;
        for (int num : map.keySet()) {
            if (map.get(num) == k) {
                ans = num;
                break;
            }
        }
        return ans;
    }

    public static int[] randomArray(int maxKinds, int range, int k, int m) {
        int kTimesNum = randomNum(range);//随机出一个数，作为真命天子。也就是出现了k次的那个数。
        int numKinds = (int) (Math.random() * maxKinds) + 2;//数组中至少有两种数
        //数组长度为：k * 1 + (numKinds - 1) * m
        int[] arr = new int[k + (numKinds - 1) * m];

        int index = 0;
        for (; index < k; index++) {
            arr[index] = kTimesNum;//k个出现了k次的kTimeNum
        }
        numKinds--;//kTimeNum这种数已经填完了，所以数字的种数要减一。
        HashSet<Integer> set = new HashSet<>();
        set.add(kTimesNum);//在set中添加第一个数，kTimesNum。
        while (numKinds != 0) {//只要数字的种类numKinds没有减到0，就一直随机生成一个数字。并将numKinds--。
            int curNum;
            do {
                curNum = randomNum(range);
            } while (set.contains(curNum));//如果随机出的数，之前已经出现过了。重新去随机生成一个数。
            set.add(curNum);
            numKinds--;
            //这种写法不好。因为这种写法的结果是，随机生成的数组只有2种不同的数字，起不到大样本随机的效果。
            /*for (; index < arr.length; index++) {
                arr[index] = curNum;
            }*/
            //一次完整的for循环走完，填m个curNum；一次完整的for循环走完，填m个curNum；知道while循环结束。
            for (int i = 0; i < m; i++) {
                arr[index++] = curNum;//index一直在++。走一次完整的for循环，index就加 m次。
            }
        }
        //arr填充完毕。
        //先不着急返回arr，此时的arr太整齐了。打乱顺序再返回。
        //让i位置的数，随机找一个数，交换。
        for (int i = 0; i < arr.length; i++) {
            int j = (int) (Math.random() * arr.length);//j在[0, arr.length - 1]上，不会越界。
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
        return arr;
    }

    //[-range, +range]。have a look。[-(range-1), +(range-1)]
    public static int randomNum(int range) {
        int num = ((int) (Math.random() * range) + 1) - ((int) (Math.random() * range) + 1);
        return num;
    }

    public static void main(String[] args) {
        int kinds = 30;
        int range = 100;
        int testTimes = 100;
        int max = 9;
        System.out.println("测试开始！");
        for (int i = 0; i < testTimes; i++) {
            int num1 = (int) (Math.random() * max) + 1;//num1属于[1, 9]
            int num2 = (int) (Math.random() * max) + 1;//num2属于[1, 9]
            int k = Math.min(num1, num2);
            int m = Math.max(num1, num2);
            if (k == m) {//必须 k<m
                m++;
            }
            int[] arr = randomArray(kinds, range, k, m);
//            System.out.println("arr = " + Arrays.toString(arr));
            int ans1 = test(arr, k, m);
            int ans2 = onlyKTimes(arr, k, m);
            if (ans1 != ans2) {
                System.out.println("oops!");
                break;
            }
        }
        System.out.println("测试结束！");
    }

    public static int onlyKTimes(int[] arr, int k, int m) {
        //先定义一个长度位为32的整数数组，叫t。
        //每一位用来标记arr中的所有num，在i位置的1出现了几个。
        int[] t = new int[32];
        //t[0] 0位置的1出现了几个
        //t[i] i位置的1出现了几个
        for (int num : arr) {
            for (int i = 0; i < 32; i++) {
                //优化写法:
                //如果(num >> i) & 1是1，t[i]就加上一个1。
                //如果(num >> i) & 1是0，t[i]就加上一个0，相当于什么都没加。
                t[i] += (num >> i) & 1;
                /**
                 * 容易理解的写法：
                 * 如果num右移i位，&上1，等于0。那么t[i]，即i位置就不加1。
                 * 如果num右移i位，&上1，等于1。那么t[i]，即i位置就加上1。
                 */
                //if ((num >> i & 1) != 0) {
                //    t[i]++;
                //}
            }
        }
        //到这儿，数组t就标记完了。
        //定义一个ans
        int ans = 0;
//        for (int i = 0; i < t.length; i++) {
        for (int i = 0; i < 32; i++) {
            //1.如果t[i] % m == 0，那么出现了k次的数字，它的第i位一定是0。
            //2.如果t[i] % m != 0，那么出现了k次的数字，它的第i位一定是1。
            //如果是第二种情况，就把这个1左移i位，"或(|)"进结果ans中。也就是标记上。
            //等for循环走完了，ans也就全部标记好了。这个ans就是出现了k次的那个num的二进制。
            //这个2个小结论的前提是，k<m。因为如果k==m，或者k>m并且k是m的倍数，这2个小结论就不成立了。
            if (t[i] % m != 0) {//在第i位上，有1
                ans |= 1 << i;
            }
        }
        return ans;
    }

//    public static void main(String[] args) {
//        int[] arr = {6, 6, 6, 6, 7, 7, 7, 7, 3, 3, 3};//6，4次。7，4次。3，3次。
//        int i = onlyKTimes(arr, 3, 4);
//        System.out.println("i = " + i);
//    }

}