【題 目】數(shù)組中有一個(gè)數(shù)字的出現(xiàn)次數(shù)超過(guò)了該數(shù)組長(zhǎng)度的一半，找出這個(gè)數(shù)字。【思 路1】由于要尋找的數(shù)字的出現(xiàn)次數(shù)超過(guò)了數(shù)組長(zhǎng)度的一半，所以如果將該數(shù)組排序，那么它的中位數(shù)必然是我們要尋找的數(shù)字，所以我們的任務(wù)就是對(duì)該數(shù)組進(jìn)行排序，而性能最好的快速排序的時(shí)間復(fù)雜度為O(nlogn)，我們可以直接借助庫(kù)函數(shù)完成，由于其效率不是很高，所以這里就不再贅述。【思 路2】對(duì)于一個(gè)數(shù)組中的元素的次數(shù)的統(tǒng)計(jì)，最快的查找方法是什么？當(dāng)然哈希表了！我們能不能建立哈希表呢，稍微思考，我們就可以發(fā)現(xiàn)，哈希表只適用于元素的范圍比較小的情況，而假設(shè)我們的數(shù)組是一個(gè)整型數(shù)組，取值范圍跨度太大，所以不適合用哈希表，太浪費(fèi)空間了。等一下，用哈希表的話，我們似乎不需要的條件是：該數(shù)字出現(xiàn)次數(shù)超過(guò)了數(shù)組長(zhǎng)度的一半？那么多了這個(gè)條件，我們能想到什么？這個(gè)數(shù)字的次數(shù)超過(guò)了其他所有數(shù)字出現(xiàn)的次數(shù)之和，所以我們?nèi)绻靡粋€(gè)key值記錄數(shù)組中的數(shù)字，然后用一個(gè)value記錄該數(shù)字出現(xiàn)的次數(shù)，然后累加：繼續(xù)遍歷余下的所有數(shù)字，如果和這個(gè)數(shù)字相等，就把次數(shù)加1；如果和這個(gè)數(shù)字不等，那么就把該數(shù)字的次數(shù)減1；如果某數(shù)字的出現(xiàn)次數(shù)為0，那么我們就用下一個(gè)數(shù)字替換之，然后重置出現(xiàn)次數(shù)為1。這樣最后剩下的數(shù)字肯定就是出現(xiàn)次數(shù)超過(guò)數(shù)組長(zhǎng)度一半的數(shù)字。好了，討論到這里我們可以很容易的寫出如下的代碼：1 #include<iostream>2 #include<string>3 using namespace std;4 5 //全局變量，檢查輸入是否有效6 bool invalidInput = false;7 8 /************************************************************9 /* 找出數(shù)組中出現(xiàn)次數(shù)超過(guò)數(shù)組長(zhǎng)度一半的數(shù)字 10 /************************************************************/ 11 int NumberAppearMoreThanHalf(int* numbers,unsigned int length) 12 { 13 if(numbers == NULL || length <= 0) 14 { 15 invalidInput = true; 16 return 0; 17 } 18 19 invalidInput = false; 20 int key = numbers[0]; 21 unsigned int appearTimes = 1; 22 for(int i = 1;i < length;++i) 23 { 24 if(appearTimes == 0) 25 { 26 key = numbers[i]; 27 appearTimes = 1; 28 } 29 30 if(numbers[i] == key) 31 appearTimes++; 32 else 33 appearTimes--; 34 } 35 36 //檢驗(yàn)輸入的數(shù)組是含有滿足條件的數(shù)字 37 appearTimes = 0; 38 for(i = 0; i < length; i++) 39 { 40 if(numbers[i] == key) 41 appearTimes++; 42 } 43 44 if(appearTimes <= length / 2) 45 { 46 invalidInput = true; 47 return 0; 48 } 49 50 return key; 51 } 52 53 int main() 54 { 55 cout<<"Enter the length of your array:"<<endl; 56 int arraylength = 0; 57 cin>>arraylength; 58 59 cout<<"Enter the elements of your array:"<<endl; 60 int *array = new int[arraylength]; 61 for(int k = 0; k < arraylength;k++) 62 { 63 cin>>array[k]; 64 } 65 66 cout<<"the number appear more than half length of your array is:"<<endl; 67 cout<<NumberAppearMoreThanHalf(array,arraylength)<<endl; 68 69 delete[] array; 70 71 return 0; 72 }
轉(zhuǎn)載自：http://www.cnblogs.com/python27/archive/2011/12/15/2289534.html

?

總結(jié)

以上是生活随笔為你收集整理的寻找数组中出现次数超过一半的数字的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。