MajorityElement [source code]

public class MajorityElement {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        if (n <= 1) return nums[0];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            Integer count = map.get(i);
            if (count == null) {
                map.put(i, 1);
            } else if (count + 1 > n / 2) {
                return i;
            } else {
                map.put(i, count + 1);
            }
        }
        return -1;
    }
}

naive 做法就是做一个counts, 然后对 counts 再单独过一遍;
这个问题之前还讨论过, 最优的做法好像是直接找 median: 可以做到 linear time and constant space;

这里实现的这个就是 naive 解法, time是 linear 的. 稍微有一点优化, 就是让算法可以提前结束, 而不是把整个 array 全都跑完;

最后的速度是46ms, 属于非常慢的了;

Problem Description

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:46.19%
Contributor: LeetCode
Companies
adobe zenefits
Related Topics
array divide and conquer bit manipulation
Similar Questions
Majority Element II