## 169. Majority Element

Given an array `nums` of size `n`, return the majority element.

The majority element is the element that appears more than `⌊n / 2⌋` times. You may assume that the majority element always exists in the array.

Example 1:

```Input: nums = [3,2,3]
Output: 3
```

Example 2:

```Input: nums = [2,2,1,1,1,2,2]
Output: 2
```

Constraints:

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

Follow-up: Could you solve the problem in linear time and in `O(1)` space?

## Rust Solution

``````struct Solution;

impl Solution {
fn majority_element(nums: Vec<i32>) -> i32 {
let mut count = 0;
let mut num: Option<i32> = None;
for x in nums {
if let Some(y) = num {
if x == y {
count += 1;
} else {
count -= 1;
if count == 0 {
num = None;
}
}
} else {
num = Some(x);
count += 1;
}
}
num.unwrap()
}
}

#[test]
fn test() {
let nums = vec![2, 2, 1, 1, 1, 2, 2];
assert_eq!(Solution::majority_element(nums), 2);
let nums = vec![3, 3, 4];
assert_eq!(Solution::majority_element(nums), 3);
}
``````

Having problems with this solution? Click here to submit an issue on github.