1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

//! Majority Element [leetcode: majority_element](https://leetcode.com/problems/majority-element/)
//!
//! Given an array of size n, find the majority element. The majority element is the element that appears **more than** `⌊ n/2 ⌋` times.
//!
//! You may assume that the array is non-empty and the majority element always exist in the array.
//!
//! ***Example1:***
//!
//! ```
//! Input: [3,2,3]
//! Output: 3
//!
//! ```
//!
//! ***Example2:***
//!
//! ```
//! Input: [2,2,1,1,1,2,2]
//! Output: 2
//! ```

use std::collections::HashMap;
/// # Solutions
///
/// # Approach 1: Hash Map
///
/// * Time complexity: O(n)
///
/// * Space complexity: O(n)
///
/// * Runtime: 12 ms
/// * Memory: 2.9 MB
///
/// ```rust
/// use std::collections::HashMap;
///
/// impl Solution {
///     pub fn majority_element(nums: Vec<i32>) -> i32 {
///         let mut map = HashMap::new();
///         let len = nums.len();
///         for num in nums {
///            let new_count = match map.get(&num) {
///                None => 1,
///                Some(x) => x+1,
///             } ;
///             if new_count * 2 >= len {
///                 return num
///             }
///             map.insert(num, new_count);
///         }
///         0
///     }
/// }
/// ```
///
/// # Approach 2: Sort
///
/// * Time complexity: O(nlgn)
///
/// * Space complexity: O(lgn)
///
/// * Runtime: 0 ms
/// * Memory: 2.9 MB
///
/// ```rust
/// impl Solution {
///     pub fn majority_element(nums: Vec<i32>) -> i32 {
///         nums.sort();
///         nums[nums.len()/2]
///     }
/// }
///
pub fn majority_element(nums: Vec<i32>) -> i32 {
    let mut map = HashMap::new();
    let len = nums.len();
    for num in nums {
       let new_count = match map.get(&num) {
           None => 1,
           Some(x) => x+1,
        } ;
        if new_count * 2 >= len { return num; }
        map.insert(num, new_count);
    }
    0
}