程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode single number

leetcode single number

編輯:關於C++

一、原題

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


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved