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.

**Naive Solution:**

Use a hash map to contain the number of each element. Then iterate the map.

**Code (Java):**

public class Solution { public int majorityElement(int[] nums) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int num : nums) { if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } int len = nums.length; Iterator it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry pair = (Map.Entry) it.next(); int key = (int) pair.getKey(); int value = (int) pair.getValue(); if (value > len / 2) { return key; } } return 0; } }

**A constant-space solution:**

Since the major element must occur more than n/2 times. We could compare each pair numbers, if not the same, we eliminate it. The left number must be the majority number.

Code (Java):

public class Solution { public int majorityElement(int[] nums) { int count = 0; int result = 0; for (int i = 0; i < nums.length; i++) { if (count == 0) { result = nums[i]; count = 1; } else if (nums[i] == result) { count++; } else { count--; } } return result; } }

## No comments:

## Post a Comment