leetcode 137
題目描述:
給定一個數組,數組中隻有一個數字隻出現一次,其餘的數字出現三次,求這個隻出現一次的數字。
輸入:一個整型數組
輸出:一個隻出現一次的數字
題目限制:
使用線性時間複雜度,常量額外空間
思路:
1.自己在思考的時候很自然想到先對數組排序,然後一次判斷前後中三個數是否相等,不相等則中間的數就是要求的隻出現一次的數。但是 時間複雜度明顯是O(nlogn),不符合要求。 我的思路代碼:
public int singleNumber1(int[] nums) {
if (nums == null || nums.length == ) {
return ;
}
Arrays.sort(nums);
int i;
for (i = ; i < nums.length; i++) {
if (nums[i]!=nums[i]&&nums[i]!=nums[i+]) {
break;
}
}
System.out.println(nums[i]);
return nums[i];
}
2.在網上看見了一個大神的解題思路。歎為觀止!基本思路是一個int數字有32位,對于二進制32位中的每一位計算“1”出現的次數隻和,如果能被三整除說明隻出現一次的那個數的二進制在該位也為0.如果不能被整除說明隻出現一次的數的二進制數在該位是“1”,再采用左移的方式還原該位,最後使用或操作“|”将結果正确求出。 大神思路代碼:
public int singleNumber(int[] nums) {
if (nums == null || nums.length == ) {
return ;
}
int res = ;
int sum = ;
for (int i = ; i < ; i++) {
sum = ;
for (int num : nums) {
int tmp = (num >> i) & ;
sum += (num >> i) & ;
}
if (sum % != ) {
res |= << i;
}
}
System.out.println(res);
return res;
}
重點
num>>i就是數字右移i位,然後與1做與運算,得出移位後最後一位是否為“1”。
如果sum不能被3整除,即 sum % 3 != 0, 則要求的數的二進制在該位為“1”。是以需要res |= 1 << i來還原。
擴充:
如果是類似的題,隻是一個出現一次,一個出現n次,可以利用相同的解法,在整除的時候更改數字即可。
zsjwish
2018年4月22日13:52:22