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

我們提供的服務(wù)有：成都網(wǎng)站制作、網(wǎng)站建設(shè)、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認證、太原ssl等。為上千余家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的太原網(wǎng)站制作公司

題目：

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

思路：

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

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

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

代碼：

class Solution {
        public int singleNumber(int[] nums) {
            //給定數(shù)組非空
            Map map = new HashMap();
            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

運行結(jié)果：

官方解答

解

異或位運算

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

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

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

思路

代碼

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

復(fù)雜度分析

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

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

復(fù)習(xí)

位運算雖然不是很常見，但是適當?shù)氖褂每梢源罅繙p少開銷。

Java中常用的位運算

&：按位與。

|：按位或。

~：按位非。

^：按位異或。

按位與

按位或

按位非

按位異或

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