算法题_位运算_9_出现一次的数字和出现k次的数字

100 阅读 0 评论 66 点赞

我是靠谱客的博主落后钢铁侠，最近开发中收集的这篇文章主要介绍算法题_位运算_9_出现一次的数字和出现k次的数字，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

位运算

出现一次的数字和出现k次的数字

题目：出现k次和出现1次
描述：数组中只有一个数出现了1次，其他的数都出现了k次，请输出只出现1次的数。

第一次看到这道题，思考了一会，觉得可以使用Map集合来做，实在想不到怎么用位运算来解决，后来同学说可以使用"不进位加法"来做，这也是用"位运算"解题的核心，因此，在此记录一下两种解法。

1、解法1（位运算）

在上面，我们提到了"不进位加法"，在解题之前，我们先补充一个知识。

如果2个相同二进制数做不进位的加法，如10+10，其结果为多少呢？很显然是：0。

那如果是10个相同十进制的数做不进位加法呢？如10个2，显然还是0。

因此我们可以得出一个小结论：k个相同的k进制数做不进位加法，其结果为0。

解法1：将所有数转为k进制，然后进行不进位的加法，最后，其结果只剩出现1次的数，再转为十进制输出即可。
    1、转为k进制
    	1.1、如何转？Java中有封装好的Integer.toString(int i, int radix)
    2、不进位加法
    	2.1、将转化的k进制数的每一位存放至二维数组中
    	2.2、遍历二维数组，将每一列做和的结果存放至另外一个整型数组中
    	2.3、遍历整型数组，对每一个元素进行取模运算，以达到不进位加法的效果
    	2.4、转化为十进制后进行累加，输出的值就为出现1次的数的值。

在这里插入图片描述

/**
 * 获取出现一次的数字
 * 解法1：位运算
 *
 * @param nums 数组
 * @param k    几个相同的数
 * @return 若存在，则返回该数
 */
public static int getOnceNumByBitOperate(int[] nums, int k) {
    //数组的长度
    int length = nums.length;
    //用二为数组来存放nums数组元素转化为k进制数的每一位
    char[][] kRadix = new char[length][];
    //转成k进制字符数组
    int maxLen = 0;
    for (int i = 0; i < length; i++) {
        /*
         * Integer.toString(nums[i], k)：转化为k进制数
         * .reverse()：将k进制字符串反转，例如21则反转为12。
         * .toString()：转化为字符串
         * .toCharArray()：将字符串转化为字符数组
         */
        kRadix[i] = new StringBuilder(Integer.toString(nums[i], k)).reverse().toString().toCharArray();
        if (kRadix[i].length > maxLen) {
            //记录最长的列，后面遍历会用到
            maxLen = kRadix[i].length;
        }
    }
    /*
     * 此数组用于存放每一个比特位做完不进位的和
     * 实际上，这里就是做了普通的加法而已，后面会对这个和进行取余操作，等价于不进位加法的效果。
     */
    int[] resArr = new int[maxLen];
    //不进位加法
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < maxLen; j++) {
            /* 如果j大于等于二位数组某一行的长度时，则+0即可。
             * j >= kRadix[i].length 也可写为 (j+1) >= kRadix[i].length
             */
            if (j >= kRadix[i].length) {
                resArr[j] += 0;
            } else {
                /*
                 * 为何要减去'0'？
                 * 因为，resArr是int类型，而kRadix数组是字符类型
                 * '0'的十进制ASCII码为48，若没有减去'0'，则会存在48的误差，比如2-0 = 0，但是 2-'0' = 2-48 = -46
                 */
                resArr[j] += (kRadix[i][j] - '0');
            }
        }
    }
    int res = 0;
    //遍历数组，拿到每个位做完加法的结果
    for (int i = 0; i < maxLen; i++) {
        /* %k：取模运算，相当于完成不进位加法的效果
         * * (int) (Math.pow(k, i))：转化为十进制
         */
        res += (resArr[i] % k) * (int) (Math.pow(k, i));
    }
    return res;
}

2、解法2（Map集合）

解法2：Map集合
    1、创建一个HashMap，键Key用来保存数组元素，值Value用来记录数组元素出现的次数
    2、遍历数组，判断Map的键是否存在
    	2.1、存在，则获取其值value，加1后
    	2.2、不存在，直接将值value设置为1
    3、遍历Map，获取所有的键key，再通过键拿到其值value
    	3.1、判断值value是否为1，若是则输出键key

/**
     * 获取出现一次的数字
     * 解法2：Map集合
     *
     * @param nums 数组
     * @return 若存在，则返回该数；反之，返回-1
     */
    public static int getOnceNum02(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        //2、遍历数组
        for (int num : nums) {
            if (map.containsKey(num)) {
                //2.1、存在
                int value = map.get(num);
                map.put(num, ++value);
            } else {
                //2.2、不存在
                map.put(num, 1);
            }
        }
        //3、遍历Map
        Set<Integer> keySet = map.keySet();
        for (Integer key : keySet) {
            //存在，返回key，即出现一次的数
            if (map.get(key) == 1) {
                return key;
            }
        }

        //不存在返回-1
        return -1;
    }

注：解法1可能比解法2晦涩难懂，效率也差，但是我认为解法1的思想还是值得学习的。

调试结果：

public static void main(String[] args) {
    //假设出现了k次
    int[] nums = new int[]{3, 3, 3, 9, 6, 6, 6, 8, 8, 8, 10, 10, 10};
    System.out.println("(位运算)出现一次的数：" + getOnceNumByBitOperate(nums, 3));
    System.out.println("(Map集合)出现一次的数：" + getOnceNumByMap(nums));
}