美文网首页
2018-08-20 LeetCode 仅出现一次的数字

2018-08-20 LeetCode 仅出现一次的数字

作者: 菜鸡学算法 | 来源:发表于2018-08-20 18:41 被阅读0次

    二进制32位中的每一位计算“1”出现的次数只和,如果能被三整除说明只出现一次的那个数的二进制在该位也为0.如果不能被整除说明只出现一次的数的二进制数在该位是“1”,再采用左移的方式还原该位,最后使用或操作“|”将结果正确求出。

    class Solution {
       public int singleNumber(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int res = 0;
            int sum = 0;
            for (int i = 0; i < 32; i++) {
                sum = 0;
                for (int num : nums) {
                    sum += (num >> i) & 1;
                }
                if (sum % 3 != 0) {
                    res |= 1 << i;
                }
            }
            System.out.println(res);
            return res;
        }
    }
    

    给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
    有两个只出现一次的数字,说明至少有一位的异或值为1,根据异或值为1的位可以把数组分为两部分,分别求这俩个部分中只出现一次的数字

    class Solution {
        public int[] singleNumber(int[] nums) {
            int[] res = new int[2];
            int length = nums.length;
            if(length == 2){
                res[0] = nums[0];
                res[1] = nums[1];
                return res;
            }
            int bitResult = 0;
            for(int i = 0; i < length; ++i){
                bitResult ^= nums[i];
            }
            int index = findFirst1(bitResult);
            for(int i = 0; i < length; ++i){
                if(isBit1(nums[i], index)){
                    res[0] ^= nums[i];
                }else{
                    res[1] ^= nums[i];
                }
            }
            return res;
        }
         
        private int findFirst1(int bitResult){
            int index = 0;
            while(((bitResult & 1) == 0) && index < 32){
                bitResult >>= 1;
                index++;
            }
            return index;
        }
         
        private boolean isBit1(int target, int index){
            return ((target >> index) & 1) == 1;
        }
    }
    

    相关文章

      网友评论

          本文标题:2018-08-20 LeetCode 仅出现一次的数字

          本文链接:https://www.haomeiwen.com/subject/ypaliftx.html