leetcode137. Single Number II

mochixuan 發(fā)布于2019-08-15 11:12 / 1035人閱讀

摘要：按照思路一和思路二很容易將這題解決。在這里，我們希望將出現(xiàn)三次的數(shù)字通過操作劃掉。之后，我們使用和分別來記錄第一位和第二位的情況。最后只出現(xiàn)一次的數(shù)值應(yīng)該是保存在中，換句話說，最后應(yīng)該全是。

題目要求

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?

假設(shè)一個數(shù)組中只有一個數(shù)字只出現(xiàn)了一遍，其它數(shù)字都出現(xiàn)了三次。返回這個只出現(xiàn)了一次的數(shù)字。

思路和代碼

在看下面的文章前，請先參考我的這篇文章關(guān)于Single Number I。按照思路一和思路二很容易將這題解決。下面要講一個通過位計算來實現(xiàn)的方法。
在這里，我們希望將出現(xiàn)三次的數(shù)字通過%3操作劃掉。比如將一個數(shù)字化為二進(jìn)制數(shù)之后，在某一位上的數(shù)字為1，則1*3%3=0，如果在某一位上為0，則0*3%3=0。也就是說，出現(xiàn)三次的數(shù)值累加的情況應(yīng)該是0->1->2->0。如果我們使用兩位來表示也就是00->01->10->00(11)。之后，我們使用b0和b1分別來記錄第一位和第二位的情況。然后我們逐位來看一下這兩位之間的關(guān)聯(lián),就可以得出下面的式子。

b0 = b0 xor r & ~b1;

b1 = b1 xor r & ~b0;

最后只出現(xiàn)一次的數(shù)值應(yīng)該是保存在b0中，換句話說，b1最后應(yīng)該全是0。

    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;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

GPU云服務(wù)器云服務(wù)器 single Leetcod LeetCode single-spa

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/67605.html

相關(guān)文章

由三道 LeetCode 題目簡單了解一下位運(yùn)算

摘要：使用位運(yùn)算數(shù)組只出現(xiàn)一次數(shù)字的數(shù)組得到最低的有效位，即兩個數(shù)不同的那一位看完上面的解法，我腦海中只有問號的存在，啥意思啊下面就讓我們簡單了解一下位運(yùn)算并解析一下這三道題目。另，負(fù)數(shù)按補(bǔ)碼形式參加按位與運(yùn)算。你可做過這幾道題？在面試的準(zhǔn)備過程中，刷算法題算是必修課，當(dāng)然我也不例外。某天，我刷到了一道神奇的題目： # 136. 只出現(xiàn)一次的數(shù)字給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外...

daydream 2019-05-21 11:41 評論0 收藏0
由三道 LeetCode 題目簡單了解一下位運(yùn)算

摘要：簡單介紹一下位運(yùn)算異或運(yùn)算異或邏輯的關(guān)系是當(dāng)不同時，輸出當(dāng)相同時，輸出。另，負(fù)數(shù)按補(bǔ)碼形式參加按位與運(yùn)算。使一個數(shù)的最低位為零，可以表示為。，截止到這兒，三道題目中使用的位運(yùn)算介紹完畢，那么這里我們插入一下的詳細(xì)題解。你可做過這幾道題？在面試的準(zhǔn)備過程中，刷算法題算是必修課，當(dāng)然我也不例外。某天，我刷到了一道神奇的題目： # 136. 只出現(xiàn)一次的數(shù)字給定一個非空整數(shù)數(shù)組，除了某個元素只...

劉明 2019-05-22 14:21 評論0 收藏0
[LintCode/LeetCode] Single Number I & II [位運(yùn)算]

摘要：整個過程相當(dāng)于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現(xiàn)過一次的，而出現(xiàn)兩次的都在里，出現(xiàn)三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 評論0 收藏0
[Leetcode] Single Number 單身數(shù)

摘要：最新思路解法請訪問排序法復(fù)雜度時間空間思路先將數(shù)組排序，再遍歷一遍，找前后都不一樣的那個數(shù)即可。代碼累加所有數(shù)中該位的個數(shù)位異或法復(fù)雜度時間空間思路我們用三個變量分別記錄出現(xiàn)一次的數(shù)，出現(xiàn)兩次的數(shù)和出現(xiàn)三次的數(shù)。 Single Number I 最新思路解法請訪問：https://yanjia.me/zh/2018/11/... Given an array of integers,...

gecko23 2019-08-14 12:27 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0