[剑指Offer]-数组中唯一只出现一次的数字

题目描述

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

这题有点意思，其他数字都重复了三次，一般位运算就消不掉了。

解题思路

• 将所有数字的二进制表示的对应位都加起来，如果某一位能被三整除，那么只出现一次的数字在该位为0；反之，为1。

算法图解

参考代码：

package offer;

/**
 * 数组中唯一个出现一次的数字，
 * 除此之外其他数字都出现了三次
 */
public class Offer56_2 {
    public static void main(String[] args) {
        int nums[] = {2, 4, 3, 2, 3, 2, 3};
        System.out.println(findAppearOnce(nums));
    }

    private static int findAppearOnce(int[] arr) {
        if (arr == null || arr.length < 4) {
            return 0;
        }
        int[] bitSum = new int[32];
        // 求每一位的和
        for (int i = 0; i < arr.length; i++) {
            int bitMask = 1;
            for (int j = 31; j >= 0; j--) {
                int bit = arr[i] & bitMask;  //注意arr[i]&bitMask不一定等于1或者0，有可能等于00010000
                if (bit != 0)
                    bitSum[j] += 1;
                bitMask = bitMask << 1;
            }
        }

        int result = 0;
        for (int i = 0; i < 32; i++) {

            result = result << 1;
            result += (bitSum[i] % 3);

        }
        return result;

    }
}

附录

该题源码在我的 ?Github 上面！

最后

以上就是完美小甜瓜为你收集整理的[剑指Offer]-数组中唯一只出现一次的数字的全部内容，希望文章能够帮你解决[剑指Offer]-数组中唯一只出现一次的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。