版权声明: 本文为博主 Bravo Yeung(知乎 Bravo Yeung)的原创文章,欲转载请先私信获博主允许,转载时请附上网址 http://blog.csdn.net/lzuacm。
在线提交: 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;
}
}
1
lxy42 2019-09-16 12:16:19 +08:00 via Android
所有元素进行 XOR 运算最后得到的就是出现一次的数字。
|
3
shiji 2019-09-16 12:55:46 +08:00 via iPhone
一楼方案的空间复杂度有绝对优势
|
4
behanga 2019-09-16 15:37:03 +08:00
确实,异或之后,不同位全位 1,而只有 1 个数字与其他不同,那么这个数字肯定就是那个 single one
|
5
qq316107934 2019-09-16 15:48:41 +08:00
JS 一行解:input.reduce((x,i) => i^x)
|