LeetCode如何查只出現(xiàn)一次的數(shù)字

這篇文章主要介紹LeetCode如何查只出現(xiàn)一次的數(shù)字，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

題目：

給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。你的算法應(yīng)該具有線(xiàn)性時(shí)間復(fù)雜度。 你可以不使用額外空間來(lái)實(shí)現(xiàn)嗎？

思路：

上次做了兩數(shù)之和的題，對(duì)hash印象還深，看到這個(gè)題的第一眼就想到hash。

遍歷數(shù)組，以當(dāng)前值為key，若當(dāng)前表中含有該數(shù)字，value為2；若不含有，value為1，遍歷完后，找表中value值為1的數(shù)字，若存在，則返回對(duì)應(yīng)key；否則，不存在這樣的數(shù)字。

空間復(fù)雜度是O(n)，不滿(mǎn)足不使用額外空間的題目要求，但我想不出什么方法辣，哭了......；

代碼：

class Solution {
        public int singleNumber(int[] nums) {
            //給定數(shù)組非空
            Map<Integer,Integer> map = new HashMap<Integer, Integer>();
            for(int i:nums)
            {
                if(map.containsKey(i))
                {
                    map.put(i,2);
                }
                else
                    map.put(i,1);
            }
            
            for(int j:map.keySet())
            {
                if(map.get(j) == 1)
                    return j;
            }
            return -1;
        }
    }

demo：

輸入：[2,2,1] 輸出：1

輸入：[4,1,2,1,2] 輸出：4

運(yùn)行結(jié)果：

官方解答

解

異或位運(yùn)算

性質(zhì)1：如果對(duì)0和二進(jìn)制位做異或運(yùn)算，得到的仍是這個(gè)二進(jìn)制位。

性質(zhì)2：如果我們對(duì)相同的二進(jìn)制位做異或運(yùn)算，返回的結(jié)果是0。

性質(zhì)3：異或運(yùn)算滿(mǎn)足交換律和結(jié)合律。

思路

代碼

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)

• 空間復(fù)雜度：O(1)

復(fù)習(xí)

位運(yùn)算雖然不是很常見(jiàn)，但是適當(dāng)?shù)氖褂每梢源罅繙p少開(kāi)銷(xiāo)。

Java中常用的位運(yùn)算

&：按位與。

|：按位或。

~：按位非。

^：按位異或。

按位與

按位或

按位非

按位異或

以上是“LeetCode如何查只出現(xiàn)一次的數(shù)字”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！