Given an array of integers, every element appears?twice?except for one. Find that single one.
這個方法重來沒見過,以后估計也不會再見了。。
1 public static int singleNumber(int[] A) { 2 int sum = 0; 3 for (int a : A) { 4 sum ^= a; 5 } 6 return sum; 7 }
leetcode121。本以為不會再見了,不過看到第二個,覺得位操作還是有些應用的。。。。
Given an array of integers, every element appears?three?times except for one. Find that single one.
還是位操作,但和上面不能一樣了。思路是,一個數如果出現了三次,那么這個數的每一位都會出現三次。那么我們可以統計下每一位一共出現多少次,再將這個數模3,剩下的數就是最后只出現一次的數。
leetcode 5,具體實施時有兩種方法:
1. 按照每一位的順序進行統計。先統計第一位一共出現多少次,模3后記錄下來,然后第二位。。。。。
1 public int singleNumber(int[] A) { 2 int result = 0; 3 for (int i=0; i<32; i++) { 4 int count = 0; 5 for (int a : A) { 6 if (((a>>i)&1) == 1) 7 count++; 8 } 9 result += (count%3)<<i; 10 } 11 return result; 12 }
?
leetcode all in one?2. 用三個整形數,one,two,three分別表示出現一次的有哪些位,出現兩次的哪些,出現三次的。。。
最后one所代表的就是只出現一次的數。
再更新one,two,three的時候要注意順序。首先要更新的是two。因為two等于上一次只出現一次的位 & 當前數字包含1的位。所以不能先更新one。
當three中某些位出現1時,把one和two中的相應的位清0。
1 public int singleNumber(int[] A) { 2 int one=0, two=0, three=0; 3 for (int a : A) { 4 two |= one & a; 5 one ^= a; 6 three = one & two; 7 one &= ~three; 8 two &= ~three; 9 } 10 return one; 11 }
?
?