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

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

  •  
  •   legege007 ·
    yanglr · 2019-09-16 12:08:34 +08:00 · 14387 次点击
    这是一个创建于 1895 天前的主题,其中的信息可能已经有所发展或是发生改变。

    版权声明: 本文为博主 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
    lxy42
        1
    lxy42  
       2019-09-16 12:16:19 +08:00 via Android
    所有元素进行 XOR 运算最后得到的就是出现一次的数字。
    legege007
        2
    legege007  
    OP
       2019-09-16 12:22:58 +08:00
    @lxy42 是的,那是另一种思路,用异或来做
    shiji
        3
    shiji  
       2019-09-16 12:55:46 +08:00 via iPhone
    一楼方案的空间复杂度有绝对优势
    behanga
        4
    behanga  
       2019-09-16 15:37:03 +08:00
    确实,异或之后,不同位全位 1,而只有 1 个数字与其他不同,那么这个数字肯定就是那个 single one
    qq316107934
        5
    qq316107934  
       2019-09-16 15:48:41 +08:00
    JS 一行解:input.reduce((x,i) => i^x)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   959 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 107ms · UTC 21:12 · PVG 05:12 · LAX 13:12 · JFK 16:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.