前言#
这题稍微要绕点脑筋
题目#
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
**进阶：**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
分析#
这道题我们直接写进阶的，既然存在时间复杂度为O(n)和空间复杂度为O(1)的解法，那就意味着只能有一层for，以及常数个变量，所以不能记录，所以我们得思考一个不需要记录的方案，即元素仅跟它前后有关系或者最大最小有关系，而这里我们是需要最多，那可以推测下可能和相加相减有关系。
是的，如果存在元素超过一半，那么它的个数减去其它元素的个数那肯定大于0。
那么一切就简单很多了，只需要两个变量，一个记录当前的状态，另一个记录上一次改变状态时的元素。
遍历结束的时候，最终的那个元素一定会是最多的那个，因为结果必定大于0。
解#
pub fn majority_element(nums: Vec<i32>) -> i32 {
let len = nums.len();
if len <= 0 {
return 0;
}
// 左边是记录的个数，右边是元素
let mut tur = (1, nums[0]);
for i in 1..len {
if tur.1 == nums[i] {
tur.0 += 1;
} else {
tur.0 -= 1;
if tur.0 == 0 {
tur.1 = nums[i];
tur.0 = 1;
}
}
if tur.0 >= (len / 2) + 1 {
break;
}
}
tur.1
}测试用例#
#[cfg(test)]
mod tests {
use super::majority_element;
#[test]
fn test_majority_element () {
assert_eq!(majority_element([3,2,3].to_vec()), 3);
assert_eq!(majority_element([2,2,1,1,1,2,2].to_vec()), 2);
}
}总结#
这道题其实有点难了，因为需要脑子绕一下。我们可以从这题里得出一些规律，如果要空间复杂度为O(1)，那么这道题要么是要最大，最小，要么元素前后有联系且除此之外没有别的联系，因为只能记录单个值。