[−][src]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] } }