数字中数字出现的次数.md

题目一

题目描述

数组中只出现一次的两个数字。

一个整型数组里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

测试用例

功能测试（数组中有多对重复的数字；数组中没有重复的数字）

解题思路

注意一次和两个这种量词，我们需要想到异或运算的一个性质：任何一个数字异或它自己都等于0。

1. 从头到尾异或数中的每个数字，得到两个只出现一次的数字的异或结果
2. 从1结果数字找到第一个为1的位的位置，记为n
3. 遍历数组，根据n位是否为1分别两组，从头到尾异或，则两组异或之后的数字即为只出现一次的两个数字。

自己解题

一脸懵逼

参考解题

/**
 * 数组中值出现一次的两个数字
 *
 * @Author rex
 * 2018/9/13
 */
public class Solution {

    /**
     * 找出数组中值出现一次的两个数字
     * @param array
     * @param num1
     * @param num2
     */
    public void findNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if (array == null || array.length < 2) {
            return;
        }
        int resultExclusiveOR = 0;
        // 1. 得到数组各个数字异或的结果
        for (int i = 0; i < array.length; i++) {
            resultExclusiveOR ^= array[i];
        }
        // 2. 找出异或结果二进制位为1的位
        int indexBit = findFirstBitIs1(resultExclusiveOR);
        // 3. 根据二进制位为1分成两部分分别异或，得到两个只出现一次的数字
        for (int i = 0; i < array.length; i++) {
            if (isBit1(array[i], indexBit)) {
                num1[0] ^= array[i];
            } else {
                num2[0] ^= array[i];
            }
        }
    }

    /**
     * 在整数num的二进制表示中找到右边是1的位
     * @param num
     * @return
     */
    public int findFirstBitIs1(int num) {
        int indexBit = 0;
        // int为32位
        while ((num & 1) == 0 && indexBit < 32) {
            num = num >> 1;
            indexBit++;
        }
        return indexBit;

    }

    /**
     * 判断num的二进制从右边数起的第indexBit是不是1
     * @param num
     * @param indexBit 从0开始
     * @return
     */
    public boolean isBit1(int num, int indexBit) {
        return ((num >> indexBit) & 1) == 1;
    }

}

题目二

题目描述

数组中唯一只出现一次的数字

在一个数组中除一个数字值出现一次之外，其他数字都出现了三次，请找出那个只出现一次的数字。

测试用例

功能测试（唯一值出现一次的数字分别为0、正数、负数；重复出现三次的数字分别是0、正数、负数）

解题思路

还是位运算解决思路。

如果一个数字出现三次，那么它的二进制表现表示的每一位也出现三次。如果把所有出现三次的数字的二进制表示的每一位都加起来，那么每一位的和都能被3整除，不能被3整除的其余数就是只出现一次的数字在该为的值。

时间复杂度为O(n) 空间复杂度为O(1)

自己解题

还是一脸懵逼。

其实做题时有点思维定势了，这其实是一道能用哈希表解决的问题(只要空间复杂度允许)。

参考解题

/**
 * 数组中唯一只出现一次的数字
 *
 * @Author rex
 * 2018/9/13
 */
public class Solution1 {
    /**
     * 数组中唯一只出现一次的数字(其他数字都出现三次)
     * @param numbers
     * @return
     * @throws Exception
     */
    public int findNumberAppearingOnce(int[] numbers) throws Exception {
        // 非法输入
        if (numbers == null || numbers.length == 0) {
            throw new Exception("invalid input");
        }
        int[] bitSum = new int[32];
        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < 32; j++) {
                if ((numbers[i] & 1) == 1) {
                    bitSum[j]++;
                }
                numbers[i] = numbers[i] >> 1;
            }
        }
        int result = 0;
        for (int i = 31; i >=0; i--) {
            result = result << 1;
            result += bitSum[i] % 3;
        }
        return result;
    }

题目考点

• 考察应聘者的知识迁移能力。
• 考察应聘者对二进制和位运算的理解。