Function leetcode_for_rust::cd0169_majority_element::majority_element

pub fn majority_element(nums: Vec<i32>) -> i32

Solutions

Approach 1: Hash Map

• Time complexity: O(n)

• Space complexity: O(n)

• Runtime: 12 ms

• Memory: 2.9 MB

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

impl Solution {
    pub fn majority_element(nums: Vec<i32>) -> i32 {
        nums.sort();
        nums[nums.len()/2]
    }
}