题意分析

  • 给出一个数组，我们需要找出在这个数组里面出现的次数超过这个数组长度的一半的那个数字。

思路分析

思路一

  • 由于需要我们求出众数，那么我们可以尝试着先进行排序，然后我们只需要遍历排好序的数组就行了，这种情况下排序的时间复杂度是,但是我们遍历的时候如果最好只要n/2+1就行，最差就是n。由于这里我们先排好序了，所以我们不需要使用map进行处理， 我们只需要用一个变量，我们遍历到的数字与前一个数字进行比较不断更新这个变量即可。

  • 代码如下

    • 由于对数组进行遍历，所以时间复杂度
    • 需要用数组存储数字，空间复杂度为O(n)
      class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
  // 先对整个数组进行排序
  sort(numbers.begin(),numbers.end());
  int cnt=1;
  int n=numbers.size();
  int ans=n/2;
  // 遍历整个数组
  for(int i=1;i<n;i++){
      // 如果这个位置的数和前一个位置的数相等
      if(numbers[i]==numbers[i-1]){
          cnt++;
          // 满足题目条件
          if(cnt>ans){
              return numbers[i];
          }
      }else{
          cnt=1;
      }
  }
  // 根据题目要求，保证这个函数有返回值，数组只有一个数字的情况才会执行这句
  return numbers[0];
}
};

思路二

  • 哈希，我们可以对每个数字进行哈希，同时记录这个数字出现的次数，然后我们就可以找到我们想要的答案了。这里可以尝试着使用一个STL里面的map来替代我们手动哈希。但是根据本人的经验，使用STL还是比较耗费时间和空间的。

  • 代码

    • 由于对数组进行遍历，所以时间复杂度O(n)
    • 需要用数组存储数字，空间复杂度为O(n) 
class Solution {
public:
    // 定义一个map存储每个数字出现的次数
    map<int,int> mp;
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n=numbers.size();
        for(int i=0;i<n;i++){
            mp[numbers[i]]++;
            // 判断是否满足题目条件
            if(mp[numbers[i]]>n/2){  
                return numbers[i];
            }
        }
        // 根据题目要求，保证这个函数有返回值，数组只有一个数字的情况才会执行这句
        return numbers[0];
    }
};

思路三

  • 第三种写法是我在第一种写法当中总结而来的，写完上面一种写法之后，我下意识认为可以不使用map进行哈希，但是反应过来没有排序。但后来仔细一想，我发现这种其实可以用一个类似于车轮战的想法。也就是我们的人海战术，我们依仗着人多的优势，同时题目又确保了我们最后的答案的个数一定超过一半。所以我们可以两个数之间两两进行比较，如果不相等，那么就直接两个数都抛弃。否则就不进行处理。这里我们可以使用一个栈进行处理。

  • 代码如下

    • 遍历数组，时间复杂度O(n)
    • 用数组存储，空间复杂度为O(n)
      class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
  // 定义一个栈来存储数据
  stack<int> st;
  // 遍历整个数组
  for(auto x:numbers) {
      // 栈为空，那么就直接放入栈里面
      if(st.empty()){
          st.push(x);
      }else{
          // 否则，比较栈顶元素的数字和当前遍历的数字，想等那么就入栈
          if(st.top()==x){
              st.push(x);
          // 不相等，那么就可以直接出栈
          }else{
              st.pop();
          }
      }
  }
  // 返回栈顶的元素即可
  return st.top();
}
};

  • 为了帮助大家更好地理解第三种写法的思路，大家可以结合这个图进行模拟，同时也可以自己造一些数据进行模拟测试。