算法题1：一个数组中1种数出现K次，其他的都出现M次，M＞1,K＜M,找到出现的K次的数，要求空间复杂度为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
package com.yypt.algorithm.class01;

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

/**
 * 一个数组中1种数出现K次，其他的都出现你M次，M>1,K<M,找到出现的K次的数，要求空间复杂度为O(1)
 */
public class Code08_KM {
    public static int onlyKTimes(int[] arr, int k, int m) {
        int[] t = new int[32];//用于存放二进制数每个位置1的个数
        for (int num : arr) {
            //将各个数转换成二进制数组
            for (int i = 0; i <= 31; i++) {
                if (((num >> i) & 1) != 0) {
                    t[i]++;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            //判断如果能不能够被m整除，说明该位置上有1
            if (t[i] % m != 0) {
                ans |= (1 << i);//将所有位置上的1拼在一起组成32位
            }
        }
        return ans;
    }

    /**
     * 对数器，用于检验程序的正确性
     * 用map实现功能
     *
     * @param arr
     * @param k
     * @param m
     * @return
     */
    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 0;
    }

    /**
     * 生成指定范围随机数
     *
     * @param range
     * @return
     */
    public static int randomNum(int range) {
        return (int) (Math.random() * range);

    }

    /**
     * 生成随机数组
     *
     * @param kinds 数的种类
     * @param k     出现k次的数
     * @param m     出现m次的数
     * @return
     */
    public static int[] randomArray(int kinds, int range, int k, int m) {
        int kNum = randomNum(range);
        int[] arr = new int[k + (kinds - 1) * m];//数组总长度
        int index = 0;
        for (int i = 0; i < k; i++) {
            arr[index++] = kNum;
        }
        kinds--;
        HashSet<Integer> set = new HashSet<>();
        set.add(kNum);
        while (kinds > 0) {
            int curNum = 0;
            do {
                curNum = randomNum(range);
            } while (set.contains(curNum));

            for (int i = 0; i < m; i++) {
                arr[index++] = curNum;
            }
            kinds--;
            set.add(curNum);
        }

        for (int i = 0; i < arr.length; i++) {
            int j = randomNum(arr.length);
            swap(arr, i, j);
        }

        return arr;
    }

    public static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;

    }

    public static void main(String[] args) {
        int kinds = 60; //数组中数的种类范围
        int range = 500;//每个数的范围
        int testTimes = 10000;//测试次数
        int maxTimes = 9; //每个数出现的最大次数
        int k = 0;
        int m = 0;
        for (int i = 0; i < testTimes; i++) {
            int a = (int) (Math.random() * maxTimes) + 1;
            int b = (int) (Math.random() * maxTimes) + 1;
            k = Math.min(a, b);
            m = Math.max(a, b);
            if (k == m) {
                m++;
            }
            int[] arr = randomArray(kinds, range, k, m);
            System.out.println(Arrays.toString(arr));
            int ans1 = test(arr, k, m);
            int ans2 = onlyKTimes(arr, k, m);
            System.out.println("map=" + ans1 + ",kTimes=" + ans2 + ",是否相等" + (ans1 == ans2));
        }
    }
}