LeetCode: Single Number Series

136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

跟我之前做的LeetCode:540那個有點像,不過這個沒有排序過

int singleNumber(int A[], int n) {
int result = 0;
for (int i = 0; i<n; i++)
{
result ^=A[i];
}
return result;
}

可以很簡單的用 xor 達成目的


137. Single Number II

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?

想不出來如何在 n 的時間內 而且又不運用額外的 space …

解法….

public int singleNumber(int[] A) {
int ones = 0, twos = 0;
for(int i = 0; i < A.length; i++){
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}
return ones;
}

起初看不懂,後來發現下面有人解釋

大概意思是說自己創一個循環是 00 -> 10 -> 01 -> 00 -> 10 …下去(因為此題最多出現三次所以第三次要循環回00) 所以用 兩個bit 存取就好了 ,所以假設 2 2 2 9 好了 ones 會先變成 2 然後第二次讀到2 twos會變成 2 ones變成 0 第三次就兩個都是 0 0 這樣的概念 (這是一個簡單的case 延伸下去也會照此規則),總之後面那些判斷是沒有算是(ones = (ones ^ A[i]) & ~twos;
 twos = (twos ^ A[i]) & ~ones;
)一定的寫法而是看你規則怎麼走 就怎麼寫。

260. Single Number III

diff&=-diff 會得到diff轉成二進位後 右邊第一個為一的bit的數

然後之後把數字分成兩堆

一堆這個bit為1的 一個是這個bit為0的

原因是 因為我把全部xor起來後 會獲得剩下兩個數的xor

因為這兩個數不一樣

所以一定會有一個bit 一邊為1 一邊為0 xor起來就為1了

所以就抓最右邊這樣的位元然後就可以分開這兩個數了

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.