1 2 3

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?

題意：一個數組中除了一個數出現一次之外，其他數都出現了三次！！找出那個出現一次的數字！！！

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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次，這樣的問題全部可以使用這樣的辦法來做。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

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; ????} }

本文轉自 努力的C 51CTO博客，原文鏈接:http://blog.51cto.com/fulin0532/1908498 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Leetcode 137. Single Number II JAVA语言的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。