隻出現一次的數字--力扣

給定一個非空整數數組，除了某個元素隻出現一次以外，其餘每個元素均出現

兩次

。找出那個隻出現了一次的元素。

說明：你的算法應該具有線性時間複雜度。 你可以不使用額外空間來實作嗎？

示例 1:

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

示例 2:

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

我的解法：

思路：首先對

nums

數組進行排序，然後判斷第 i 個元素和該元素的前後兩個元素是否相等，如果跟前後兩個元素都不相等，則答案就是該元素。這樣解決問題有一個弊端就是，需要考慮

數組越界

問題。

出現的問題：

1. 第一個元素沒有之前的元素，最後一個元素沒有之後的元素，是以就需要分情況考慮
2. 是以我就分了三種情況：①目前元素是第一個元素 ②目前元素既不是第一個元素也不是最後一個元素 ③目前元素是最後一個元素
3. 數組的長度為 1 時，應當直接傳回這個元素.

public int singleNumber(int[] nums) {
        Arrays.sort(nums);//對數組進行排序
        int len = nums.length;//數組的長度
        int ans = nums[0];//記錄答案，初始化為第 0 号元素的值
        if (len == 1) return ans;//數組長度為1
        for (int i = 0; i < len; i++) {
            //是第一個元素
            if (i == 0 && nums[i]!=nums[i+1]){
            }
            //既不是第一個，也不是最後一個
            if (i != 0 && i != len-1){
                if (nums[i]!=nums[i-1]&&nums[i]!=nums[i+1]){
                    ans = nums[i];
                }
            }
            //最後一個元素
            if (i == len-1 && nums[i] != nums[i-1]){
                ans = nums[i];
            }
        }
        return ans;
    }
           

看了别人做的後，突然感覺自己真實太傻了！-

人家的解法：

• 使用異或運算，将所有值進行異或
• 異或運算，相異為真，相同為假，是以

  a^a = 0 ;0^a = a

• 因為異或運算 滿足交換律

  a^b^a = a^a^b = b

  是以數組經過異或運算，單獨的值就剩下了

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

雖然不知道底層的異或具體怎麼實作的，但是這樣做太簡單了！不用排序，直接将每個元素都進行異或，最後就是答案了！

注意：這樣做也是有條件的，必須保證出現重複元素的次數必須是偶數次才能保證這種解法是正确的。恰好改題目說的是

除了某個元素隻出現一次以外，其餘每個元素均出現兩次

雖然這道題目比較簡單，但是我覺我們應該學會從每道題目中學到一些沒見過的、有趣的東西！