「众数」【LeetCode】寻找众数（绝对众数、1/k众数） - Medium

众数

1.已知给定的N个整数A[1…N]存在绝对众数，以最低的时空复杂度计算该绝对众数。

(若某众数出现次数多于n/2，则称作绝对众数),

【分析】

删除数组A中两个不同的数，绝对众数不变。

若两个数中有1个是绝对众数，则剩余的N-2个数中，绝

对众数仍然大于(N-2)/2；

若两个数中没有绝对众数，显然不影响绝对众数。

算法描述：

记m为候选绝对众数，出现次数为c，初始化为0。

遍历数组A：

若c==0，则m=A[i]；

若c≠0且m≠A[i]，则同时删掉m和A[i]；

若c≠0且m==A[i]，则c++；

绝对众数是指在数列 a中出现次数严格大于 N / 2 的数。

求绝对众数的几种方法：

(1)快速排序

快速排序之后在数列中间的数是绝对众数

(2)摩尔投票法

摩尔投票法的基本思想很容易理解，在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。循环执行这一操作，直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半（无绝对众数）。如果只存在一种元素，那么这个元素则可能为绝对众数。

在编写算法的过程中，我们可以直接按照数组原来的顺序进行投票，删除。

具体实现：

设 m为当前出现阶段超过半数的元素（候选数），cnt 为此元素出现次数。由于有了阶段的概念，这其实这也是一种动态规划思想。

①一开始 m 直接为数组第一个元素， cnt=1。（原因是只有一个元素的数组，唯一的那个元素一定是绝对众数）

接着遍历数列 a，设当前数为a[i]。

②若 a[i]=m，则 cnt++。

③若a[i]≠m，则我们可以把当前候选数m和当前数a[i]同时删除，具体操作只需让cnt–，这样就相当于忽略了数a[i] && 删去一个候选值m。 (因为for循环 i++后，a[i]自然更新其值，无需考虑之前a[i]的删除，故忽略a[i]的删除)

④若cnt=0，则重新选择候选值：表明前一阶段并没有出现次数超过半数的元素。假设绝对众数存在，那么绝对众数一定在剩余的数组中是绝对众数，这样我们只需要求解原始问题的子问题即可，即在后一阶段的绝对众数是多少。回到开始，m 为当前元素，cnt=1。

最终，若cnt>0，则m 可能为候选元素。扫一遍数组确认一下即可。

复杂度为线性的，O(n)。

#include <iOStream>
#include <cstdlib>
using namespace std;

int Mode(int* a, int size){
    int cnt = 0;
    int m = a[0];
    for(int i = 0; i<size; i++){
        if(cnt == 0){
            m = a[i];
            cnt = 1;
        }else if(m != a[i]){

        }else{// m == a[i]
            cnt++;
        }
    }
    return m;
}

int main()
{
    int a[] = {8,1,1,8,1,1,6,1,5,8,8};
    int m = Mode(a, sizeof(a)/sizeof(int));
    cout<<m<<endl;
    return 0;
}

二、1/k 众数、 [要求：时间复杂度O(N), 空间复杂度O(k)]

1、如k=3时,求给定数组中的1/3众数。（即该众数的出现次数> N/3）

注：有可能这样的数不存在。

要求：时间复杂度O(N), 空间复杂度O(1)

    #include <iostream>
    #include <cstdlib>
    #include <vector>
    #include <iterator>
    using namespace std;

    void FindMode(const int *a, int size, vector<int>& mode){
  int m,n;//候选值
  int cm = 0, cn = 0;//候选值m、n的个数
  int i;
  for(i=0; i<size; i++){
    if(cm == 0){
      m = a[i];
      cm = 1;
    }else if(cn == 0){
      n = a[i];
      cn = 1;
    }else if(m == a[i]){
      cm++;
    }else if(n == a[i]){
      cn++;
    }else{
      cm--;
      cn--;
    }
  }
  //↑ 运行到此处时的m、n一定是众数，同时也是可能存在的1/3众数。
 
  cm = cn = 0;//为确保一定存在（因为1/3众数可能不存在），一定要重新遍历统计出现次数
  for(i=0; i<size; i++){
    if(m == a[i]){
      cm++;
    }else if(n == a[i]){
      cn++;
    }
  }
  if(cm > size/3){
    mode.push_back(m);
//    cout<< m<<" ";
  }
  if(cn > size/3){
    mode.push_back(n);
//    cout<< n<<" ";
  }
 
}

void print(vector<int> vector){
  for(int i=0; i<vector.size(); i++){
    cout<< vector[i]<<" ";
  }
  cout<<endl;
}

int main()
{
  int a[] = {8,1,1,8,1,1,6,1,5,8,8};
  vector<int> mode;
  FindMode(a, sizeof(a)/sizeof(int),mode);
  Print(mode);
  return 0;
}

【LeetCode】寻找众数（绝对众数、1/k众数） - Medium

众数

相关阅读

栏目导航

推荐阅读

热门阅读