本文共 712 字，大约阅读时间需要 2 分钟。

算法的基本思想

我们讨论的算法是用来解决一个典型问题：从一个数组中找出出现次数超过半数的元素。这个算法的基本原理是，每次找出一对不同的元素，并从数组中删除它们，直到数组为空或者只剩下一种元素。这个算法的核心思想是：如果有一个元素的出现次数超过半数，那么经过一系列删除操作后，最后剩下的就是那个元素。

算法的实现

以下是这个算法的具体实现代码：

int majorityElement(vector
   
    & num) {    int curIdx = 0, count = 1;    for (int i = 1; i < num.size(); ++i) {        if (num[i] == num[curIdx]) {            ++count;        } else {            --count;        }        if (count == 0) {            curIdx = i;            count = 1;        }    }    return num[curIdx];}
   

这个算法通过维护当前元素和当前计数来工作。每当遇到与当前元素不同的元素时，计数器就会减少。如果计数器减少到零，则表示当前元素已经被删除，接着我们将当前索引设置为当前元素的位置，并重新初始化计数器为1。

这种方法的时间复杂度是O(n)，因为它只需要遍历数组一次。空间复杂度是O(1)，因为它只使用了几个额外的变量。

通过这种方式，我们可以快速找到数组中出现次数超过半数的元素。这个算法在实际应用中非常有效，常用于解决类似的问题。