Given an 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?
题目
给定一个整数数组，里面只有一个数只出现一次，其余的数都出现两次，找出只出现一次的数。
方法
采用异或运算^
a ^ a = 0
a ^ 0 = a
a ^ b ^ c = a ^ (b ^ c)
c代码
#include <assert.h>
int singleNumber(int* nums, int numsSize) {
int i = 0;
int single = 0;
for(i = 0; i < numsSize; i++) {
single ^= nums[i];
}
return single;
}
int main() {
int nums[5] = {1,3,3,1,5};
assert(singleNumber(nums, 5) == 5);
return 0;
}
网友评论