一个由于数字组成的数组，里面的数字除了一个都出现了两次。找到那个只有一个的数字。
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
我想象就像打扑克牌，排序一样。从里面找相同的放在一起。换位置。于是写了如下的方法。
public int SingleNumber(int[] nums) {
for (int i = nums.Length - 1; i >= 0; i--)
{
if (i % 2 != 0) return nums[i + 1];
for (int j = i - 1; j >= 0; j--)
{
if (nums[j] == nums[i])
{
nums[j] = nums[i - 1];
nums[i - 1] = nums[i];
i = i - 1;
break;
}
}
}
return nums[0];
}
提交被accept以后 Your runtime beats 7.09 % of csharp submissions
然后点前面人的一看。哇靠就一行。震惊了。但是不太明白这种二进制的位运算。
public int SingleNumber(int[] nums) {
return nums.Aggregate( (x, y) => x ^ y);
}
重学一下^ 就是如果两个数二进制的相同（1同1 0同0）那么按位异或就是零。不同才是1。如果这么算我难道不要排序么？
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
我想象就像打扑克牌，排序一样。从里面找相同的放在一起。换位置。于是写了如下的方法。
public int SingleNumber(int[] nums) {
for (int i = nums.Length - 1; i >= 0; i--)
{
if (i % 2 != 0) return nums[i + 1];
for (int j = i - 1; j >= 0; j--)
{
if (nums[j] == nums[i])
{
nums[j] = nums[i - 1];
nums[i - 1] = nums[i];
i = i - 1;
break;
}
}
}
return nums[0];
}
提交被accept以后 Your runtime beats 7.09 % of csharp submissions
然后点前面人的一看。哇靠就一行。震惊了。但是不太明白这种二进制的位运算。
public int SingleNumber(int[] nums) {
return nums.Aggregate( (x, y) => x ^ y);
}
重学一下^ 就是如果两个数二进制的相同（1同1 0同0）那么按位异或就是零。不同才是1。如果这么算我难道不要排序么？
