leetcode121，LeetCode: Single Number I II

2023-10-07 阅读 27 评论 0

摘要：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 retur

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     }