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

57 阅读 0 评论 38 点赞

我是靠谱客的博主暴躁时光，最近开发中收集的这篇文章主要介绍算法题1：一个数组中1种数出现K次，其他的都出现M次，M＞1,K＜M,找到出现的K次的数，要求空间复杂度为O(1)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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));
        }
    }
}