1.问题描述

快速找出发帖超过一半的的ID

问题变型：

现在有一个数组，已知一个数出现的次数超过了一半，请用最小的复杂度的算法找出这个数。

问题扩展：

有三个发帖很多的ID，他们的发帖数目超过了帖子总数目的1/4，请从发帖ID列表中找出它们

 

 

2.分析与解法

每次从列表中删除两个不同的ID，那么剩下的ID列表中，“水王”的ID出现次数仍然超过剩余数目的一半，因此每次删除两个不同的ID，直到剩下的所有ID都相同，那么剩下的就是水王的ID。

我们可以设置一个candidate和一个计数器nTimes，candidate为ID列表第一个ID，nTimes初始值为0，遍历整个ID列表，当遍历的ID与candidate相同，nTimes++，如果不同则nTimes--，此时相当于成对删除不同的ID，当nTimes又为0的时候，更新candidate，将其设置为当前遍历的ID，因为有一个ID总是在剩余中的ID超过一半，所以最后nTimes大于0，candidate即为所求。

int find(int* ID, int n){    int nTimes = 0, i, candidate;        for(i = 0; i < 0;i++)    {          if(nTimes == 0)          {              candidate = ID[i];          }          else          {              if(candidate == ID[i])              {                  nTimes++;              }              else              {                  nTimes--;              }          }    }        return candidate;}

扩展问题：依据以上的原理，我们可以以四个为单位进行比较，如果四个ID均不相同则删掉四个ID，那么所要求的三个ID，仍然超过其余ID的1/4。

相应的代码实现:

void find3(int * ID, int n)  {      int candidate[3];     int nTimes[3] = {
   0};      int i;        for (i = 0; i < n; i++)      {          if(nTimes[0] == 0)          {              if(ID[i] == candidate[1])                  nTimes[1]++;              else if (ID[i] == candidate[2])                  nTimes[2]++;              else              {                  candidate[0] = ID[i];                  nTimes[0]++;              }          }          else if (nTimes[1] == 0)          {              if(ID[i] == candidate[0])                  nTimes[0]++;              else if (ID[i] == candidate[2])                  nTimes[2]++;              else              {                  candidate[1] = ID[i];                  nTimes[1]++;              }          }          else if (nTimes[2] == 0)          {              if(ID[i] == candidate[0])                  nTimes[0]++;              else if (ID[i] == candidate[1])                  nTimes[1]++;              else              {                  candidate[2] = ID[i];                  nTimes[2]++;              }          }          else          {              if(ID[i] == candidate[0])                  nTimes[0]++;              else if(ID[i] == candidate[1])                  nTimes[1]++;              else if(ID[i] == candidate[2])                  nTimes[2]++;              else                  nTimes[0]--, nTimes[1]--, nTimes[2]--;          }      }        printf("三个水王ID分别是:%d,%d,%d\n", candidate[0], candidate[1], candidate[2]);  }