今天将介绍一个寻找主元素的算法。

问题 1

假设给出一个长度为n的数组，数组中的元素为整型类型的数字，其中一个数字出现的概率 > n/2，即出现超过一半，如何找出这个数字呢？

思路

这里我们将使用“消除法”来解这个问题。假设我们有数组[1, 1, 2, 1, 3, 2, 1]，我们从数组中逐一找出不同的一对数字进行消除：

这样的话，由于主元素的个数 > n/2，因此在逐对消除的过后，主元素必将是留存下来的，而留存下来的也必将是主元素。

如果按照上图的思路来写，算法是需要O(n * n)的时间复杂度的。我们可以稍稍改变一下思路，使其达到O(n)的时间复杂度：

这里是这个解法的代码：

const find = function find(arr) {  const count = arr.length;  let v1;  let score1;  for (let i = 0; i < arr.length; i++) {    const v = arr[i];    if (v1 === null) {      v1 = v;      score1 = 1;    } else if (v1 === v) {      score1++;    } else {      score1--;      if (score1 === 0) {        v1 = null;      }    }  }  return v;};复制代码

问题 2

现在我们将问题改变一下，假设有两个主元素，每个元素出现的概率 > n/3，那么如何找到这个主元素呢？

思路是相同的，只要我们尝试找出每一组3个互不相同的元素进行消除，那么剩余两个元素就应当是主元素了：

这里我们贴上修改后的代码：

const find = function find(arr) {  const count = arr.length;  let v1;  let v2;  let score1;  let score2;  for (let i = 0; i < arr.length; i++) {    const v = arr[i];    if (v1 === null && v2 !== v) {      v1 = v;      score1 = 1;    } else if (v2 === null && v1 !== v) {      v2 = v;      score2 = 1;    } else if (v1 === v) {      score1++;    } else if (v2 === v) {      score2++;    } else {      score1--;      score2--;      if (score1 === 0) v1 = null;      if (score2 === 0) v2 = null;    }  }  return v;};复制代码

扩展问题

最后我们将问题扩展为，如果在长度为n的数组中，存在x个主元素，它们的出现概率 > n/(x+1)，那么如何找出这些主元素呢？

这里我们就可以直接用一个Map来代替之前的v1、v2这些变量了，代码如下：

const find = function find(arr, x) {  const count = arr.length;  let map = new Map();  for (let i = 0; i < arr.length; i++) {    const v = arr[i];    const has = map.has(v);    if (!has) {      if (map.size < x) {        map.set(v, 1);      } else {        for ([val, score] of map.entries()) {          if (score === 1) {            map.delete(val);          } else {            map.set(val, score - 1);          }        }      }    } else {      map.set(v, map.get(v) + 1);    }  }  return v;};复制代码