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] 通過測試案例

重構測試代碼: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;
        }
    }

通過 LeetCode 上所有測試案例

結論

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

GitHub commit history: LeetCode_136_Single_Number

對敏捷開發有興趣的朋友,可以參考我的粉絲專頁:91敏捷開發之路

若需要聯絡我,可以透過粉絲專頁私訊或是側欄的關於我。