LeetCode. 136 Single Number

LeetCode 136 題：Single Number

題目描述

題目解釋：給一個整數陣列 nums, 裡面只有一個數字出現一次，其他都是出現兩次，找出那個孤單的數字。

Step 1: 新增測試用例，只有一個整數時，回傳該整數。nums_is_5_singleNumber_should_be_5

測試代碼：

測試代碼

生產代碼：

尚未實作的生產代碼

Step 2: Hard-code return nums[0] 以通過測試用例

生產代碼：先直接回傳 nums[0] 以通過測試用例

hard-code 通過測試用例

重構測試代碼：[Extract Method] AssertSingleNumber()

重構測試：擷取驗證方法

Step 3: 新增測試用例，nums_is_454_singleNumber_should_be_5

測試代碼：整數陣列長度增加到 3。

長度為 3 的測試用例

生產代碼：使用 Dictionary 來存放每個數字出現的次數為奇數還是偶數。

用 Dictionary 紀錄數字出現次數為奇數還是偶數

Step 4: 新增通過的測試用例

測試用例：

        [TestMethod]
        public void nums_is_454_singleNumber_should_be_5()
        {
            var nums = new int[] { 4, 5, 4 };
            AssertSingleNumber(nums, 5);
        }

        [TestMethod]
        public void nums_4_2_4_7_2_singileNumber_should_be_7()
        {
            var nums = new int[] { 4, 2, 4, 7, 2 };
            AssertSingleNumber(nums, 7);
        }

題目有說明，不希望用到額外的記憶體來處理，因此 Dictionary 是不符合題目規定的。

Step 5: 重構演算法，改用 XOR 處理，找出孤單的數字

XOR 的特色是，某個數字 XOR 偶數次，會得到全都是 0 的結果。最後剩下的，就是孤單的數字。

生產代碼：

    public class Solution
    {
        public int SingleNumber(int[] nums)
        {
            int result = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                result = result ^ nums[i];
            }

            return result;
        }
    }

通過 LeetCode 上所有測試用例

通過 LeetCode 所有 test cases

結論

就是考你 XOR 的特性，沒啥太大意義。但練手感跟思路還是不錯的。

GitHub commit history: LeetCode_136_Single_Number