LeetCode. 136 Single Number

2017-03-10

887
0
LeetCode 練功房
2017-03-13

LeetCode 136 題：Single Number

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

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

測試代碼：

生產代碼：

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

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

重構測試代碼：extract method AssertSingleNumber()

Step 3: 新增測試案例，nums_is_454_singleNumber_should_be_5

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

生產代碼：使用 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;
        }
    }