前言

这题稍微要绕点脑筋

题目

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

示例 2：

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

**进阶：**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

分析

这道题我们直接写进阶的，既然存在时间复杂度为O(n)和空间复杂度为O(1)的解法，那就意味着只能有一层for，以及常数个变量，所以不能记录，所以我们得思考一个不需要记录的方案，即元素仅跟它前后有关系或者最大最小有关系，而这里我们是需要最多，那可以推测下可能和相加相减有关系。

是的，如果存在元素超过一半，那么它的个数减去其它元素的个数那肯定大于0。

那么一切就简单很多了，只需要两个变量，一个记录当前的状态，另一个记录上一次改变状态时的元素。

遍历结束的时候，最终的那个元素一定会是最多的那个，因为结果必定大于0。

解

测试用例

总结

这道题其实有点难了，因为需要脑子绕一下。我们可以从这题里得出一些规律，如果要空间复杂度为O(1)，那么这道题要么是要最大，最小，要么元素前后有联系且除此之外没有别的联系，因为只能记录单个值。