LeetCode 169 Majority Element (Java)

Source url: 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 exists in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

We provide 3 solutions. Hash-map approach, divide and conquer approach and sort approach.

Hash-map approach

This solution is easily understood, we use a hash-map to store counts of elements. The first loop we count every element. The second loop we find the most frequency element, it is our result. Actually, we can use one loop to get the result, a little faster, but it will not change the complexity, so we ignore it.

Divide and conquer approach

Because the majority element appears more than half times, so we know if we split the array to left and right, it will be one of the majority element in left or right. So we can use divide and conquer approach, cut again and again until only one element, just Mergesort problem.

Sort approach

First, we sort the array, then one loop to count elements. (And there are a more easy solution, sort and get the middle element, it must be the majority element.)

Github address: https://github.com/tinyfool/leetcode/tree/master/src/p0169

Want to know details of the Divide and conquer, check my post: Leetcode problems of Divide and conquer.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.