leetcode137. Single Number II

mochixuan 發布于2019-08-15 11:12 / 1024人閱讀

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

題目要求

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?

假設一個數組中只有一個數字只出現了一遍，其它數字都出現了三次。返回這個只出現了一次的數字。

思路和代碼

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

b0 = b0 xor r & ~b1;

b1 = b1 xor r & ~b0;

最后只出現一次的數值應該是保存在b0中，換句話說，b1最后應該全是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;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 single Leetcod LeetCode single-spa

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67605.html

由三道 LeetCode 題目簡單了解一下位運算

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

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

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

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

摘要：整個過程相當于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現過一次的，而出現兩次的都在里，出現三次的都被消去了。 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 單身數

摘要：最新思路解法請訪問排序法復雜度時間空間思路先將數組排序，再遍歷一遍，找前后都不一樣的那個數即可。代碼累加所有數中該位的個數位異或法復雜度時間空間思路我們用三個變量分別記錄出現一次的數，出現兩次的數和出現三次的數。 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 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 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