LeetCode-只出现一次的数字

一、只出现一次的数字Ⅱ

题目：给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

思路：将所有数字加起来，记录下每一位二进制加过的次数，其余每个元素都出现了三次，则每位二进制的次数都是3次/4次/0次。每一位都对3取余，剩下的二进制就是只出现一次元素的二进制了。

问题来了，怎么保存二进制呢？用一个大小为32的int类型数组保存。

代码：

public int singleNumber(int[] nums) {
        int[] count = new int[32];
        //统计每一位出现的次数
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < count.length; j++){
                count[j] += nums[i] & 1;
                nums[i] >>>= 1; 
            }
        }
        //对3取余，剩下的count[]就是只出现一次的数的二进制位表示
        for(int i = 0; i < count.length; i++){
            count[i] %= 3;
        }
        int res = 0;
        /**
        这里一定是res先左移一位，再和二进制相与，否则得到的结果是两倍的res
        */
        for(int i = 0; i < count.length; i++){
            res <<= 1;
            res |= count[31-i];
        }
        return res;
    }

二、只出现一次的数字Ⅲ

题目：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

思路：几个月前听左程云讲的方法，要用到异或。

（异或：位相同为0，不同为1。例如：a ^ a = 0，a ^ b ^ b = a）

1、将数组中所有的元素异或，得到的结果res就是出现一次的两个元素的异或。

2、两个不同的元素，异或的结果一定不是0，他们一定有一位不为0，找到第一个不为0的位（不是第一位也可以，但至少找到一个）。数组中所有的元素，被分为两组：第一组的该位是0，第二组的该位是1。再次遍历数组，该位是0的异或在一起，该位是1的异或在一起。最后得到的两个结果就是两个只出现一次的数字

代码：

public int[] singleNumber(int[] nums) {
        //找出两个元素异或的结果
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            res = nums[i] ^ res;
        }
        //此时res是两个数异或的结果
        //找到不同的一位，该为不同，是1
        int basic = 1;
        while((basic & res) == 0){
            basic <<= 1;
        }
        int num1 = 0;
        int num2 = 0;
        for(int i = 0; i < nums.length; i++){
            if((nums[i] & basic) == 0){
                num1 = num1 ^ nums[i];
            } else{
                num2 = num2 ^ nums[i];
            }
        }
        return new int[]{num1,num2};
    }

更新：int basic  = res & (-res)；res & (-res) 能得到最右边为1的数

最后

以上就是善良紫菜为你收集整理的LeetCode-只出现一次的数字的全部内容，希望文章能够帮你解决LeetCode-只出现一次的数字所遇到的程序开发问题。

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