首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  LeetCode

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

  •  
  •   legege007 · 81 天前 · 4395 次点击
    这是一个创建于 81 天前的主题,其中的信息可能已经有所发展或是发生改变。

    版权声明: 本文为博主 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 实用技术实战噢~

    5 回复  |  直到 2019-09-16 15:48:41 +08:00
        1
    lxy42   81 天前 via Android
    所有元素进行 XOR 运算最后得到的就是出现一次的数字。
        2
    legege007   81 天前
    @lxy42 是的,那是另一种思路,用异或来做
        3
    shiji   81 天前 via iPhone
    一楼方案的空间复杂度有绝对优势
        4
    behanga   80 天前
    确实,异或之后,不同位全位 1,而只有 1 个数字与其他不同,那么这个数字肯定就是那个 single one
        5
    qq316107934   80 天前
    JS 一行解:input.reduce((x,i) => i^x)
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4012 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 20ms · UTC 07:15 · PVG 15:15 · LAX 23:15 · JFK 02:15
    ♥ Do have faith in what you're doing.