一、原题

Given an array of integers, every element appears twice except for one. Find that single one.

int singleNumber(int *nums, int numsSize)

?

二、举例来说

nums[numsSize] ::: nums[5] = {2, 1, 1, 1, 1}

题目要求返回的值就是其中只出现一次的数，也就是2

?

三、具体解决办法

题目要求在线性时间内解决问题。

方法一、

我首先想起的是算法导论的计数排序，把每个数值出现的次数统计一下，输出只出现一次的就可以了，但是结果runtime error，而后仔细观察，发现这个方法没法对nums[]中值是负的值计数，我放弃了这种方法，但觉得这种方法还是很值得学习的。

?

#include 
  
   
#include 
   
     //#define numSize 5 int singleNumber(int *nums, int numsSize){ int i; int MaxNum = nums[0]; int count[1000]; //find MaxNum of nums[] for(i = 1; i < numsSize; i++){ if(nums[i] > MaxNum){ MaxNum = nums[i]; } } //initialize count[i] for(i = 0; i <= MaxNum; i++){ count[i] = 0; } //count nums[i] for(i = 0; i < numsSize; i++){ count[nums[i]] = count[nums[i]] + 1; //printf("i: %d, nums[i]: %d, count[nums[i]]: %d\n", i, nums[i], count[nums[i]]); } /*for(i = 0; i <= MaxNum; i++){ printf("i: %d, apperas times: %d\n", i, count[i]); } printf("\n");*/ //find the num appear once for(i = 0; i <= MaxNum; i++){ if(count[i] == 1){ return nums[i]; } //else{ // return 0; //} } } int main(){ int nums[21] = {17,12,5,-6,12,4,17,-5,2,-3,2,4,5,16,-3,-4,15,15,-4,-5,-6}; int i; i = singleNumber(nums, 21); printf("difference num is: %d\n", i); system("pause"); return 0; }
   
  

?

?

方法二、

参考别人博客写的，是通过异或实现的，有这样的规则：相同的数异或值为0，任何数与0异或都是该数本身，所以可以写代码了，这个是在leetcode上通过的。

?

#include 
  
   
#include 
   
     int singleNum(int *nums, int numsSize){ int i; int result = 0; for(i = 0; i < numsSize; i++){ result = result ^ nums[i]; } return result; } int main(){ int nums[21] = {17,12,5,-6,12,4,17,-5,2,-3,2,4,5,16,-3,-4,15,15,-4,-5,-6}; int result; result = singleNum(nums, 21); printf("%d\n", result); system("pause"); return 0; }
   
  

?

看到accepted是不是很happy呢，不要因为是参考别人的想法，自己就懒得做，亲们，要加油！