【面试题39：数组当中数字超过一半的数字】

求数组当中元素个数超过一半的数字，例如一个长度为7的数组：{1,2,2,2,2,4,5}；其中元素2的个数为4，长度超过了一半；

我的做法是：（假设输入是vector<int> vec）构建一个map<int, int>；key对应vec当中元素，value对应vec当中元素出现次数。我们遍历vec_,然后直接执行map_[ele_]++。遍历完之后，再遍历map就很容易找出这个数。

 1 int MoreThanHalfNum_Solution1(vector<int>& vec_)
 2 {
 3     // 异常处理
 4     if (vec_.empty())
 5         return -1;
 6 
 7     map<int, int> map_;
 8     for (auto ele_ : vec_)
 9     {
10         map_[ele_]++;
11     }
12 
13     int half_num_ = vec_.size() / 2;
14     for (auto ele_ : map_)
15     {
16         if (ele_.second > half_num_)
17         {
18             return ele_.first;
19         }
20     }
21     // 可能不存在这样的数
22     return -1;
23 }

这种做法的缺点是：我在这里利用了map这种关联容器。在插入新元素的时候，如果已经存在相同key的元素，这时候会插入失败。不管怎样，插入新元素的时候，都会遍历map一次。

改进做法：例如：对于数组{1，1,1,2,2,3,4,4,4,4}；遍历数组，设置times_ = 0；

1、如果当前元素和上一个元素相同，则 times_ ++；

2、如果当前元素和上一个元素不同，则 times_ --；

3、如果times_ = 0，则将上一个元素刷新为当前元素，times_ = 1;

 1 //统计元素 result_ 在 vec_数组当中是否超过半数
 2 bool CheckMoreHalf(vector<int>& vec_, int retsult_)
 3 {
 4     if (vec_.empty())
 5         return -1;
 6 
 7     int count = 0;
 8     for (auto ele_:vec_)
 9     {
10         if ( ele_ == retsult_)
11         {
12             count++;
13         }
14     }
15 
16     if (2*count >= vec_.size())
17     {
18         return true;
19     }
20     else
21     {
22         return false;
23     }
24 
25 }

View Code

 1 int MoreThanHalfNum_Solution2(vector<int>& vec_)
 2 {
 3     if (vec_.empty())
 4         return -1;
 5 
 6     int ret_ = vec_[0];
 7     int times_ = 1;
 8     for (auto ele_:vec_)
 9     {
10         if (times_ == 0)
11         {
12             ret_ = ele_;
13             times_ = 1;
14         }
15         else if (ele_ == ret_)
16             times_++;
17         else
18             times_--;
19     }
20     if (!CheckMoreHalf(vec_, ret_))
21     {
22         ret_ = -1;
23     }
24     return ret_;
25 }

方法2的优点是时间复杂度明显是O（n）；其实方法1的时间复杂度表面上看是O（n）；由于每一次循环都会调用map底层排序（基于红黑树）。所以，方法一的复杂度远不止O（n）；有关几种常用排序算法，这里不作讨论了。

现在我们做实验，将数组size设置到20000+

  1 #include<map>
  2 #include<vector>
  3 #include<iostream>
  4 
  5 using namespace std;
  6 
  7 #include<boost/timer.hpp>
  8 
  9 int MoreThanHalfNum_Solution1(vector<int>& vec_)
 10 {
 11     // 异常处理
 12     if (vec_.empty())
 13         return -1;
 14 
 15     map<int, int> map_;
 16     for (auto ele_ : vec_)
 17     {
 18         map_[ele_]++;
 19     }
 20 
 21     int half_num_ = vec_.size() / 2;
 22     for (auto ele_ : map_)
 23     {
 24         if (ele_.second > half_num_)
 25         {
 26             return ele_.first;
 27         }
 28     }
 29     // 可能不存在这样的数
 30     return -1;
 31 }
 32 
 33 //统计元素 result_ 在 vec_数组当中是否超过半数
 34 bool CheckMoreHalf(vector<int>& vec_, int retsult_)
 35 {
 36     if (vec_.empty())
 37         return -1;
 38 
 39     int count = 0;
 40     for (auto ele_:vec_)
 41     {
 42         if ( ele_ == retsult_)
 43         {
 44             count++;
 45         }
 46     }
 47 
 48     if (2*count >= vec_.size())
 49     {
 50         return true;
 51     }
 52     else
 53     {
 54         return false;
 55     }
 56 
 57 }
 58 
 59 int MoreThanHalfNum_Solution2(vector<int>& vec_)
 60 {
 61     if (vec_.empty())
 62         return -1;
 63 
 64     int ret_ = vec_[0];
 65     int times_ = 1;
 66     for (auto ele_:vec_)
 67     {
 68         if (times_ == 0)
 69         {
 70             ret_ = ele_;
 71             times_ = 1;
 72         }
 73         else if (ele_ == ret_)
 74             times_++;
 75         else
 76             times_--;
 77     }
 78     if (!CheckMoreHalf(vec_, ret_))
 79     {
 80         ret_ = -1;
 81     }
 82     return ret_;
 83 }
 84 
 85 int main()
 86 {
 87     vector<int> vec_{ 1,3,4,5,6,6,6,6,6,6,6,2,7 };
 88     for (int i = 0; i < 20000; i++)
 89     {
 90         vec_.push_back(8);
 91     }
 92 
 93     boost::timer timer1;
 94     cout << "MoreThanHalfNum_Solution1 : " << MoreThanHalfNum_Solution1(vec_) << endl;
 95     cout << "the cost of time is:" << timer1.elapsed() << endl;
 96 
 97     boost::timer timer2;
 98     cout << "MoreThanHalfNum_Solution2 : " << MoreThanHalfNum_Solution2(vec_) << endl;
 99     cout << "the cost of time is:" << timer2.elapsed() << endl;
100 
101     return 1;
102 }

Debug X64模式：

以上四次实验：从上往下，输入数组规模一次增大，分别为：2000、4000、20000、40000；

可以看到第二种算法速度总是第一种的5倍以上；所以，c++ STL虽然用起来舒服，但是还是要站在效率的角度上，适当使用STL，且要用对、用准相应容器类型。