面试题29：数组中出现次数超过一半的数字

 1 int partition(vector<int>&num, int low, int high)
 2 {
 3     int pivot = num[low];
 4     while (low < high)
 5     {
 6         while (low < high && num[high]>=pivot)
 7             --high;
 8         num[low] = num[high];
 9         while (low < high && num[low]<=pivot)
10             ++low;
11         num[high] = num[low];
12     }
13     num[low] = pivot;
14     return low;
15 }
16 bool isInputInvalid = false;
17 int moreThanHalfNum(vector<int>&num)
18 {
19     int n = num.size();
20     //检查输入是否有效
21     if (n==0)
22     {
23         isInputInvalid = true;
24         return 0;
25     }
26     int left = 0;
27     int end = num.size()-1;
28     int middle = n/2;
29     int index = partition(num,left,right);
30     while (index!=middle)
31     {
32         if (index < middle)
33         {
34             left = index+1;
35             index = partition(num,left,right);
36         }
37         else
38         {
39             right = index-1;
40             index = partition(num,left,right);
41         }
42     }
43     //确认找到的数字出现的次数超过数组的一半
44     int temp = 0;
45     for (int i = 0; i < n; ++i)
46     {
47         if ( num[i] == num[index] )
48             ++temp;
49     }
50     if (temp <= middle)
51     {
52         isInputInvalid = true;
53         return 0;
54     }
55     return num[index];
56 }

 1 bool isInputInvalid = false;
 2 int moreThanHalfNum(vector<int>&num)
 3 {
 4     unordered_map<int,int>m;
 5     int n = num.size();
 6     //检查输入是否有效
 7     if (n==0)
 8     {
 9         isInputInvalid = true;
10         return 0;
11     }
12     for (int i = 0; i < n; ++i)
13     {
14         if (m.count(num[i]))
15             m[num[i]]++;
16         else
17             m[num[i]]=1;
18         if (m[num[i]] > n/2)
19             return num[i];
20     }
21     isInputInvalid = true;
22     return 0;    
23 }