LeetCode如何查只出現一次的數字

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

題目：

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

思路：

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

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

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

代碼：

class Solution {
        public int singleNumber(int[] nums) {
            //給定數組非空
            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

運行結果：

官方解答

解

異或位運算

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

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

性質3：異或運算滿足交換律和結合律。

思路

代碼

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

復雜度分析

• 時間復雜度：O(n)

• 空間復雜度：O(1)

復習

位運算雖然不是很常見，但是適當的使用可以大量減少開銷。

Java中常用的位運算

&：按位與。

|：按位或。

~：按位非。

^：按位異或。

按位與

按位或

按位非

按位異或

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