一个数组中有一种数出现了K次，其他数都出现了M次，且 M＞1,K＜M 。找到出现了K次的数，要求额外空间复杂度O(1)，时间复杂度O(N)

118 阅读 0 评论 78 点赞

我是靠谱客的博主矮小超短裙，这篇文章主要介绍一个数组中有一种数出现了K次，其他数都出现了M次，且 M＞1,K＜M 。找到出现了K次的数，要求额外空间复杂度O(1)，时间复杂度O(N)，现在分享给大家，希望可以做个参考。

复制代码

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
    public static void main(String[] args) {
        //一个数组中有一种数出现了K次，其他数都出现了M次，且 M>1,K<M 。找到出现了K次的数，要求额外空间复杂度O(1)，时间复杂度O(N)
        //k = 2 ，M = 4
        int[] arr = new int[]{111, 200, 30000001, 4, 111, 200, 30000001, 4, 111, 200, 30000001, 4, 111, 200, 30000001, 4, 5, 5, 10086, 10086, 10086, 10086};
        int k = 2;
        int m = 4;

        System.out.println(method(arr,k,m));
    }

    public static int method(int[] nums, int k, int m) {
        int[] t = new int[32];
        for (int i = 0; i < 32; i++) {
            for (int num : nums) {
                t[i] += (num >> i) & 1;
            }
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int num = t[i];
            num %= m;
            num /= k;
            res += num << i;
        }
        return res;
    }