leetcode136.只出現(xiàn)一次的數(shù)字
題目描述：
給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次阅签。找出那個只出現(xiàn)了一次的元素。
說明：
你的算法應(yīng)該具有線性時間復雜度酱鸭。 你可以不使用額外空間來實現(xiàn)嗎揩局？
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
思路：異或運算
對于異或運算有以下特性：
- a ^ a = 0
- a ^ 0 = a
已知非空數(shù)組中，只有某個元素出現(xiàn)了一次廉沮，其余的元素均出現(xiàn)了兩次。所以徐矩，我們可以從頭讓每個元素依次進行異或運算滞时，一直遍歷到最后一個元素，異或的結(jié)果就是那個只出現(xiàn)一次的元素滤灯。代碼如下：
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i = 0; i < nums.length; ++i){
res ^= nums[i];
}
return res;
}
}
時間復雜度：O(N)
額外空間復雜度：O(1)
代碼執(zhí)行結(jié)果：
leetcode 137.只出現(xiàn)一次的數(shù)字ii
題目描述：
給定一個非空整數(shù)數(shù)組坪稽，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)了三次鳞骤。找出那個只出現(xiàn)了一次的元素窒百。
說明：
你的算法應(yīng)該具有線性時間復雜度。 你可以不使用額外空間來實現(xiàn)嗎豫尽？
示例 1:
輸入: [2,2,3,2]
輸出: 3
示例 2:
輸入: [0,1,0,1,0,1,99]
輸出: 99
思路：位運算
對于題目的示例：
[2,2,3,2]
轉(zhuǎn)換為二進制后：
10
10
11
10
每一位上對1的個數(shù)進行統(tǒng)計篙梢，如果能整除3，那么返回結(jié)果的那一位則為0美旧；如果不能整除3渤滞，那么返回結(jié)果的那一位則為1：
10
10
11
10
第一位的和為1，第二位的和為4榴嗅，都不能整除3妄呕，所以結(jié)果為：
11
返回的結(jié)果轉(zhuǎn)換為十進制后，也正好為只出現(xiàn)一次的那個元素
代碼如下：
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i = 0;i < 32;i++){
int temp = 0;
for(int num : nums){
temp += (num >>> i) & 1;
}
if(temp % 3 != 0){
res |= (1 << i);
}
}
return res;
}
}
時間復雜度：O(N)
額外空間復雜度：O(1)
代碼執(zhí)行結(jié)果：
