成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode136. Single Number

zhaot / 1612人閱讀

摘要：題目要求如何在使用的時(shí)間復(fù)雜度和的額外空間復(fù)雜度來(lái)找到一個(gè)數(shù)組中唯一一個(gè)成單的數(shù)字。思路一可以通過(guò)來(lái)記錄數(shù)字出現(xiàn)的情況。如果已經(jīng)出現(xiàn)，則將其從中刪除。一個(gè)數(shù)值和另一個(gè)數(shù)值進(jìn)行兩次異或計(jì)算，該數(shù)值不變。

題目要求 
Given an array of integers, every element appears twice except for one. Find that single one.

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

如何在使用O(n)的時(shí)間復(fù)雜度和O(0)的額外空間復(fù)雜度來(lái)找到一個(gè)數(shù)組中唯一一個(gè)成單的數(shù)字。

思路一：hashset

可以通過(guò)set來(lái)記錄數(shù)字出現(xiàn)的情況。如果set中不曾出現(xiàn)該數(shù)字，則加入set。如果已經(jīng)出現(xiàn)，則將其從set中刪除。最后無(wú)法從set中刪除的數(shù)字，則是single number

    public int singleNumber(int[] nums) {
        Set set = new HashSet();
        for(int i = 0 ; i i = set.iterator() ; i.hasNext() ; ) single = i.next();
        return single;
    }
思路二：排序

如果將array排序后，那么相同的數(shù)字一定位于相鄰的位置上，只需要比較2k和2k+1位置上的值是否相同就可以了。

    public int singleNumber2(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0 ; i
思路三：bit manipulation

這里就需要提一下異或這個(gè)操作符。一個(gè)數(shù)值和另一個(gè)數(shù)值進(jìn)行兩次異或計(jì)算，該數(shù)值不變。也就是說(shuō)： A XOR B XOR B = A XOR （B XOR B） =  A
在這里也可以試一下具體數(shù)值。
其實(shí)異或的話，可以用白話來(lái)說(shuō)就是‘要么這個(gè)，要么那個(gè)’
所以也就是說(shuō)，如果將array中的所有數(shù)值都進(jìn)行一次異或計(jì)算，那么最終的結(jié)果也就是那個(gè)singleNumber。


    public int singleNumber3(int[] nums) {
        for (int i =1; i < nums.length; i++) {
            nums[i] ^= nums[i-1];
        }
        return nums[nums.length-1];
    }



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

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

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

相關(guān)文章

  • Leetcode PHP題解--D51 136. Single Number

    摘要：題目鏈接題目分析返回給定數(shù)組中，只出現(xiàn)了一次的元素。思路用計(jì)算元素出現(xiàn)的次數(shù)。最終代碼若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。 D51 136. Single Number 題目鏈接 136. Single Number 題目分析 返回給定數(shù)組中，只出現(xiàn)了一次的元素。 思路 用array_count_values計(jì)算元素出現(xiàn)的次數(shù)。 再用array_search返回出現(xiàn)次數(shù)為1的元素。...

    KunMinX 評(píng)論0 收藏0

  • 由三道 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 評(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è)元素只...

    劉明 評(píng)論0 收藏0

  • leetcode部分題目答案之JavaScript版

    摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項(xiàng)目地址 自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

    alphahans 評(píng)論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

    摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

zhaot

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<