程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Leetcode :: Single Number II

Leetcode :: Single Number II

編輯:C++入門知識

Leetcode :: Single Number II


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


Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?


題意很明了,重點在於要求線性時間和常數額外空間,single number I 是把所有都異或,最後就是答案,很明了;可是這裡有3個,應該怎麼辦呢?

出現了三次的時候,如果仍然從位運算入手,特征是什麼?設那個唯一的數是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;
    }

這裡be careful two可以用異或,因為不可能出現one two在相同位同時為1的情況,所以異或和或是一樣的,但是邏輯上,應該是選用或 ,更能表現這個算法的意思;

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved