C#刷遍 LeetCode 系列 - No.136. Single Number - 题解

[legege007]

版权声明: 本文为博主 Bravo Yeung(知乎 Bravo Yeung)的原创文章，欲转载请先私信获博主允许，转载时请附上网址 http://blog.csdn.net/lzuacm。

C#版 - Leetcode 136. Single Number - 题解

136. Single Number

在线提交: https://leetcode.com/problems/single-number/

---

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

---

思路: 使用 Dictionary<int, int>存储每一个整数出现的次数即可，然后从里面挑出第一个出现次数为 1 的 KeyValuePair 的 Key 值。

已 AC 代码:

public class Solution {
    public int SingleNumber(int[] nums) {
            int res = 0;
            Dictionary<int, int> dict = new Dictionary<int, int>();
            foreach (var num in nums)
            {
                if (!dict.ContainsKey(num))
                {
                    dict.Add(num, 1);
                }
                else
                    dict[num]++;
            }

            res = dict.FirstOrDefault(kv => kv.Value == 1).Key;

            return res;
    }
}

更多干货可关注 公号「 dotNET 匠人」，持续输出优质的 .NET 学习文章~

Bravo Yeung 还会携手数位 ●NET 技术大佬在知乎专栏 dotNET 学堂 与你一起学习 ●NET 实用技术实战噢~

[lxy42]

所有元素进行 XOR 运算最后得到的就是出现一次的数字。

[legege007]

@lxy42 是的，那是另一种思路，用异或来做

[shiji]

一楼方案的空间复杂度有绝对优势

[behanga]

确实，异或之后，不同位全位 1，而只有 1 个数字与其他不同，那么这个数字肯定就是那个 single one

[qq316107934]

JS 一行解：input.reduce((x,i) => i^x)