瀏覽標籤:

XOR

[C#][LeetCode][Easy] 136. Single Number

心得:

從數字陣列中找出只有出現過一次的數字並傳出,這題原本我想說很簡單用一句LinQ就可以交差了,結果一個超時QQ…
最後看了Top Solution還是不太懂只好求助古狗大神並尋求朋友協助,最後才理解了數學的奇妙 !!

解題思路:

2017-01-08-23_04_32-%e9%82%8f%e8%bc%af%e7%95%b0%e6%88%96-%e7%b6%ad%e5%9f%ba%e7%99%be%e7%a7%91%ef%bc%8c%e8%87%aa%e7%94%b1%e7%9a%84%e7%99%be%e7%a7%91%e5%85%a8%e6%9b%b8
根據XOR的真值表,我們用陣列[1, 2, 3, 4, 1, 2, 3]來測試,轉換為二進位的話則是[001, 010, 011, 100, 001, 010, 011]接著運算如下:
^ = 運算子 = XOR

  1. 001 ^ 010 = 011
  2. 011 ^ 011 = 000
  3. 000 ^ 100 = 100
  4. 100 ^ 001 = 101
  5. 101 ^ 010 = 111
  6. 111 ^ 011 = 100
  7. 100 轉十進位則是 4,由此可知答案是4

問題:

Given an array of integers, every element appears twice except for one. Find that single one.

答案:

  1. Normal
    public class Solution {
        public int SingleNumber(int[] nums) {
            int ans = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                ans ^= nums[i];
            }
            return ans;
        }
    }
  2. LinQ (Time Out)
    public class Solution {
        public int SingleNumber(int[] nums) {
            return nums.Where(x => nums.Count(y => x == y) == 1).SingleOrDefault();
        }
    }

參考:

  1. 邏輯異或
  2. 大神朋友