leetcode single number

leetcode single number

一、原題

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呢，不要因為是參考別人的想法，自己就懶得做，親們，要加油！