GitHub
簡書
CSDN

題目

給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。

說明
你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現(xiàn)嗎？

示例1

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

示例2

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

難度系數(shù): 簡單

解題思路一

常規(guī)方法是,遍歷數(shù)組,然后統(tǒng)計每個值出現(xiàn)的次數(shù),最后在選擇出現(xiàn)次數(shù)為1的那個值.該算法的時間復雜度為O(N),首先是統(tǒng)計數(shù)組,此時要遍歷整個數(shù)組,然后是要遍歷我們的統(tǒng)計數(shù)組,此時有事一個O(N),由于我們使用了一個統(tǒng)計數(shù)組來保存每個值出現(xiàn)的次數(shù),此時需要的空間復雜度為O(n),因此不符合要求.

解題思路二

為了解決不需要額外的空間這個要求,我們可以使用位操作中的異或規(guī)則來進行處理.異或運算法則如下

1. a a = 0, a 0=a
2. a b = b a
3. a b c = a (b c) = a (c b) = (a b) c

其中,第一條規(guī)則說明,當某個數(shù)出現(xiàn)兩次時,通過 變?yōu)?,出現(xiàn)一次時依然保持原來的數(shù),第二、三條的交換律和分配律說明通過多次 操作最終解決本題。

注意: 本體題目中指出除了某個元素值出現(xiàn)一次外其余的均出現(xiàn)兩次，根據(jù)法則一可以看出本算法只適合除了某個元素出現(xiàn)一次外，其余元素出現(xiàn)偶數(shù)次的情況。

比如在示例二中的 操作：

Java實現(xiàn)代碼

/**
 * @author Maosong Ran
 * @date 2018/10/06
 * @email maosongran@gmail.com
 */
public class LeetCode_136 {
    public int singleNumber(int[] nums) {
        int result = 0;
        int len = nums.length;
        for (int i=0; i < len; ++i)
            result ^= nums[i];
        return result;
    }

    public static void main(String[] args) {
        LeetCode_136 leetCode = new LeetCode_136();
        System.out.println(leetCode.singleNumber(new int[]{2, 2, 1}));
        System.out.println(leetCode.singleNumber(new int[]{4, 1, 2, 1, 2}));
    }
}

輸出:

1
4

致謝

感謝大家的閱讀和支持, 歡迎大家上星..