首页 > 代码库 > Leetcode 137. Single Number II JAVA语言

Leetcode 137. Single Number II JAVA语言

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题意:一个数组中除了一个数出现一次之外,其他数都出现了三次!!找出那个出现一次的数字!!!

public class Solution {
    public int singleNumber(int[] nums) {
        int ret=0;
        int[] count=new int[32];
        int len=nums.length;
        for(int i=0;i<32;i++){
            for(int j=0;j<len;j++){
            //统计所有数字第i位0,1的和。通过右移与1做&运算得到!!!!!!
                count[i]+=((nums[j]>>i)&1);
             ////然后把对于位的和取模3就得到了single数字的第i位哦
                count[i]=count[i]%3;
            }
            ////因为之前左移了i位,所以现在右移回来,然后与0做或|运算
            ////所有的1就可以归为了!!!!!我曹真是6666
            ret |=(count[i]<<i);
        }
        return ret;
    }
}

PS:本来看了左老师的书,本来以为可以用K进制无进位加法做来着。详情见左老师书。但是不知道为什么不能通过。所以就上网扒拉了一个比较通用的方法。

输入是int型数组,所以可以用32位来表达输入数组的元素。
假设输入中没有single number,那么输入中的每个数字都重复出现了数字,也就是说,对这32位中的每一位i而言,所有的输入加起来之后,第i位一定是3的倍数。
现在增加了single number,那么对这32位中的每一位做相同的处理,也就是说,逐位把所有的输入加起来,并且看看第i位的和除以3的余数,这个余数就是single numer在第i位的取值。这样就得到了single number在第i位的取值。这等价于一个模拟的二进制,接着只需要把这个模拟的二进制转化为十进制输出即可。
为了完成上面的过程,需要使用一个数组 int a[ 32 ]来模拟位运算。
可以看出来,这个做法对于功力的要求非常高,需要看到数字的时候,眼前展现的是数字背后的二进制组成,要不然很难想到可以逐位去处理。
另外,这个做法可以扩展,如果有一堆输入,其中1个数字出现了1次,剩下的数字出现了K次,这样的问题全部可以使用这样的办法来做。

public class Solution {
    public int singleNumber(int[] nums) {
        //if(nums==null || nums.length<4)return 0;
        int[] ret=new int[32];
        for(int i=0;i!=nums.length;i++){
            sum3(ret,nums[i]);
        }
        return gain101(ret);
        
    }
    public static void sum3(int[] ret,int nums){
        // int[] ret=new int[32];
        // for(int i=0;i<nums.length;i++){
        //   int[] cur=to3(nums[i]);
        //     for(int j=0;j<cur.length;j++){
        //         ret[j]=(ret[j]+cur[j])%3;
        //      }  
        // }
        int[] cur=to3(nums);
        for(int i=0;i!=ret.length;i++){
            ret[i]=(ret[i]+cur[i])%3;
        }
        //return ret;
    }
    public static int[] to3(int num){
        int[] ret=new int[32];
        int index=0;
        while(num!=0){
            ret[index++]=num%3;
            num=num/3;
        }
        return ret;
    }
    // public static int gain10(int[] arr){
    //     int ret=0;
    //     int temp=0;
    //     for(int i=0;i<arr.length;i++){
    //         temp=(int)Math.pow(3,i);
    //         ret=ret+arr[i]*temp;
    //     }
    //     return ret;
    // }
    public static int gain101(int[] arr){
        int ret=0;
        for(int i=arr.length-1;i!=-1;i--){
            ret=ret*3+arr[i];
        }
        return ret;
    }
}


Leetcode 137. Single Number II JAVA语言