Topic

• Array
• Divide and Conquer
• Bit Manipulation

Description

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 exist in the array.

Example 1:

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

Example 2:

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

Analysis

方法一：使用排序

方法二：使用HashMap

方法三：Moore投票算法（我認為眾多方法中最優的）

方法四：位操作

方法五：硬幣正反算法（賭運氣，挺有趣）

方法六：分治算法

Submission

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;public class MajorityElement {// 方法一：使用排序public int majorityElement1(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}// 方法二：使用Hashtablepublic int majorityElement2(int[] nums) {Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();// Hashtable<Integer, Integer> myMap = new Hashtable<Integer, Integer>();int ret = 0;for (int num : nums) {if (!myMap.containsKey(num))myMap.put(num, 1);elsemyMap.put(num, myMap.get(num) + 1);if (myMap.get(num) > nums.length / 2) {ret = num;break;}}return ret;}// 方法三：Moore 投票算法public int majorityElement3(int[] nums) {int count = 0, ret = 0;for (int num : nums) {if (count == 0)ret = num;if (num != ret)count--;elsecount++;}return ret;}// 方法四：位操作1public int majorityElement4_1(int[] nums) {int[] bit = new int[32];for (int num : nums)for (int i = 0; i < 32; i++)if ((num >> (31 - i) & 1) == 1)bit[i]++;int ret = 0;for (int i = 0; i < 32; i++) {bit[i] = bit[i] > nums.length / 2 ? 1 : 0;ret += bit[i] * (1 << (31 - i));}return ret;}// 方法四：位操作2public int majorityElement4_2(int[] nums) {int majority = 0;for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) {int bits = 0;for (int num : nums) {if ((num & mask) > 0) {bits++;}}if (bits > nums.length / 2) {majority |= mask;}}return majority;}// 方法五：概率計算public int majorityElement5(int[] nums) {int n = nums.length, candidate = 0;while (true) {candidate = nums[(int) (Math.random() * n)];int counter = 0;for (int num : nums) {if (num == candidate) {counter++;}}if (counter > n / 2) {break;}}return candidate;}// 方法六：分治算法public int majorityElement6(int[] nums) {return findMajority(nums, 0, nums.length - 1);}private int findMajority(int[] nums, int low, int high) {if (low == high)return nums[low];int mid = low + (high - low) / 2;int left = findMajority(nums, low, mid);int right = findMajority(nums, mid + 1, high);if (left == right)return left;int countLeft = getFreq(nums, left, low, mid);int countRight = getFreq(nums, right, mid + 1, high);if (countLeft > countRight)return left;return right;}private int getFreq(int[] nums, int val, int low, int high) {int res = 0;for (int i = low; i <= high; i++) {if (nums[i] == val)res++;}return res;}}

Test

import static org.junit.Assert.*;
import org.junit.Test;public class MajorityElementTest {@Testpublic void test() {MajorityElement obj = new MajorityElement();int[][] array = {{1, 1, 1, 1, 1, 3, 4, 5}, {3, 2, 3}, {2, 2, 1, 1, 1, 2, 2}};assertEquals(1, obj.majorityElement1(array[0]));assertEquals(3, obj.majorityElement1(array[1]));assertEquals(2, obj.majorityElement1(array[2]));assertEquals(1, obj.majorityElement2(array[0]));assertEquals(3, obj.majorityElement2(array[1]));assertEquals(2, obj.majorityElement2(array[2]));assertEquals(1, obj.majorityElement3(array[0]));assertEquals(3, obj.majorityElement3(array[1]));assertEquals(2, obj.majorityElement3(array[2]));assertEquals(1, obj.majorityElement4_1(array[0]));assertEquals(3, obj.majorityElement4_1(array[1]));assertEquals(2, obj.majorityElement4_1(array[2]));assertEquals(1, obj.majorityElement4_2(array[0]));assertEquals(3, obj.majorityElement4_2(array[1]));assertEquals(2, obj.majorityElement4_2(array[2]));assertEquals(1, obj.majorityElement5(array[0]));assertEquals(3, obj.majorityElement5(array[1]));assertEquals(2, obj.majorityElement5(array[2]));assertEquals(1, obj.majorityElement6(array[0]));assertEquals(3, obj.majorityElement6(array[1]));assertEquals(2, obj.majorityElement6(array[2]));}
}