數組中出現2次

假設你有一個用1001個整數組成的數組，這些整數是任意排列的，但是你知道所有的整數都在1到1000(包括1000)之間。此外，除一個數字出現兩次外，其他所有數字只出現一次。假設你 只能對這個數組做一次處理 ，用一種算法找出重復的那個數字。 如果你在運算中使

分析：

方法一、若使用輔助的存儲方式，該選擇何種存儲方式呢？可使用hash的存儲方式，以1到1000作為hash表的索引，遍歷原數組，統計各數字出現的個數并存儲到以該數字為索引值的hash表中，若某個hash[x]的值為2則退出循環，x就是重復出現兩次的數字。時間復雜度最壞是O(n)。優點：高效率，缺點：消耗的內存空間過大。代碼如下：

[cpp] view plaincopyprint?

1. int fun1(const int a[])
2. {
3. int hash[1002]={0};
4. int x=0;
5. for(int i = 0; i<1001; i++)
6. {
7. if((++hash[a[i]]) == 2)
8. {
9. x = a[i];
10. break;
11. }
12. }
13. return x;
14. }

int fun1(const int a[])
{
 int hash[1002]={0};
 int x=0;
 for(int i = 0; i<1001; i++)
 {
 if((++hash[a[i]]) == 2)
 	{
 	 x = a[i];
 	 break;
 	}
 }
 return x;
}

方法二、若不使用輔助的存儲方式呢？已知1001個整數組成的數組只有一個數字出現了兩次，且整數都在1到1000之間，所以可推得數組里面包含了1到1000之間的所有數字為[1,2,3……1000]和一個出現兩次的x為1到1000中的任一個數字。這樣就可以計算原數組里的所有數字之和S1和等差數列[1,2,3……1000]的和S2，再計算S1與S2之差，該差就是原數組中出現兩次的數字x。時間復雜度是固定的O(n)。優缺點：內存空間消耗幾乎沒有，但是效率要輸于使用hash表的存儲方式。代碼如下：

[cpp] view plaincopyprint?

1. int fun2(const int a[])
2. {
3. int s1=0,s2;
4. s2 = 1001*1000/2;
5. for(int i = 0; i<1001; i++)
6. {
7. s1+=a[i];
8. }
9. return s1-s2;
10. }

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com