一、原題
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呢,不要因為是參考別人的想法,自己就懶得做,親們,要加油!