leetcode137. Single Number II

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

摘要：按照思路一和思路二很容易將這題解決。在這里，我們希望將出現(xiàn)三次的數(shù)字通過(guò)操作劃掉。之后，我們使用和分別來(lái)記錄第一位和第二位的情況。最后只出現(xiàn)一次的數(shù)值應(yīng)該是保存在中，換句話(huà)說(shuō)，最后應(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è)一個(gè)數(shù)組中只有一個(gè)數(shù)字只出現(xiàn)了一遍，其它數(shù)字都出現(xiàn)了三次。返回這個(gè)只出現(xiàn)了一次的數(shù)字。

思路和代碼

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

b0 = b0 xor r & ~b1;

b1 = b1 xor r & ~b0;

最后只出現(xiàn)一次的數(shù)值應(yīng)該是保存在b0中，換句話(huà)說(shuō)，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;
    }

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

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/67605.html

相關(guān)文章

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

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

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

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

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

摘要：整個(gè)過(guò)程相當(dāng)于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現(xiàn)過(guò)一次的，而出現(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 評(píng)論0 收藏0
[Leetcode] Single Number 單身數(shù)

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

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

摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言?xún)?nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱(chēng)和地址。本許可協(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 評(píng)論0 收藏0