出現了三次的時候,如果仍然從位運算入手,特征是什麼?設那個唯一的數是x,特征是,按int型32位計,其中某一位假設x在該位上是0,則情況應該是該位的1出現的次數是3的倍數,而如果是1,則應該是出現3n + 1次的1,根據這個特征,來計算那個唯一的數據;
設三個int, one、two、three,這裡出現一次為 0 1 兩次未 1 0 三次為 1 1 這裡的高位是存在two中,低位存在one中,根據不同狀態去做操作;同時為1則清0. 再強調一下,這裡one表示的每一位在低位的計數表示,two表示每一位在高位的計數表示;
public: int singleNumber(int A[], int n) { int one = 0, two = 0, three = 0; for (int i = 0; i < n; i++){ two |= one & A[i]; //be careful one ^= A[i]; three = one & two; one &= ~three; two &= ~three; } return one; }