leetcode260. Single Number III

Terry_Tai 發布于2019-08-15 14:19 / 275人閱讀

摘要：要求我們找到這兩個數字。舉例解釋一下第二個位運算一個數的負數是通過計算其正數的補碼獲得的。比如的八位二進制為，那么其反碼為，再在反碼上加一得到其補碼也就是的二進制形式。從而獲得二進制最右側的位置。

題目要求

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

假設一個整數數組中，除了兩個數字以外，所有的數字都出現了兩遍。要求我們找到這兩個數字。

可以先參考Single Number I 和 Single Number II。

思路與代碼

這里需要了解兩個位運算的重要知識：

a^b^b = a 即b^b=0
a&(-a)能夠獲得a的二進制形式的最右側的1的位置。

舉例解釋一下第二個位運算：
一個數的負數是通過計算其正數的補碼獲得的。比如5的八位二進制為00000101，那么其反碼為11111010，再在反碼上加一得到其補碼11111011也就是-5的二進制形式。
那么我們可以知道，一個數與其反碼的與運算，得出的結果一定為0。而反碼加一則代表著將原數的最后一位1在反碼上也置為1。從而獲得二進制最右側1的位置。

    public int[] singleNumber(int[] nums) {
       int diff = 0;
        for(int num : nums){
            diff ^= num;
        }
        
        diff &= -diff;
        
        int[] result = {0, 0};
        for(int num : nums){
            if((num & diff) == 0){
                result[0] ^= num;
            }else{
                result[1] ^= num;
            }
        }
        return result; 
    }

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

GPU云服務器云服務器 III single Leetcod LeetCode

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

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

[LintCode/LeetCode] Single Number III

摘要：去掉最后一個保留最后一個保留最后一個保留第一個這道題在論壇里參考了和兩位仁兄的解法。思想是將中所有的數進行異或運算。不同的兩個數異或的結果，一定至少有一位為。最后，將和存入數組，返回。 Problem Given 2*n + 2 numbers, every numbers occurs twice except two, find them. Example Given [1,2,2...

lanffy 2019-08-14 15:33 評論0 收藏0
由三道 LeetCode 題目簡單了解一下位運算

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

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

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

劉明 2019-05-22 14:21 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
[LeetCode] 557. Reverse Words in a String III

Problem Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1:Input: Lets take LeetCode contest...

104828720 2019-08-16 13:33 評論0 收藏0