leetcode136. Single Number

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

摘要：題目要求如何在使用的時間復雜度和的額外空間復雜度來找到一個數(shù)組中唯一一個成單的數(shù)字。思路一可以通過來記錄數(shù)字出現(xiàn)的情況。如果已經(jīng)出現(xiàn)，則將其從中刪除。一個數(shù)值和另一個數(shù)值進行兩次異或計算，該數(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)的時間復雜度和O(0)的額外空間復雜度來找到一個數(shù)組中唯一一個成單的數(shù)字。

思路一：hashset

可以通過set來記錄數(shù)字出現(xiàn)的情況。如果set中不曾出現(xiàn)該數(shù)字，則加入set。如果已經(jīng)出現(xiàn)，則將其從set中刪除。最后無法從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
這里就需要提一下異或這個操作符。一個數(shù)值和另一個數(shù)值進行兩次異或計算，該數(shù)值不變。也就是說： A XOR B XOR B = A XOR （B XOR B） =  A
在這里也可以試一下具體數(shù)值。
其實異或的話，可以用白話來說就是‘要么這個，要么那個’
所以也就是說，如果將array中的所有數(shù)值都進行一次異或計算，那么最終的結果也就是那個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ā)技術，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關注我的微信公眾號！將會不定期的發(fā)放福利哦~

云服務器 GPU云服務器 136企業(yè)網(wǎng)盤 single Leetcod LeetCode

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

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

Leetcode PHP題解--D51 136. Single Number

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

KunMinX 2019-07-01 12:44 評論0 收藏0
由三道 LeetCode 題目簡單了解一下位運算

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

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

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

劉明 2019-05-22 14:21 評論0 收藏0
leetcode部分題目答案之JavaScript版

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

alphahans 2019-08-21 16:20 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

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