LeetCode - Easy - 169. Majority Element-蒲公英云

LeetCode - Easy - 169. Majority Element

桃扇骨 2022-12-29 09:53 214阅读 0赞

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];
    }
    // 方法二：使用Hashtable
    public 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);
            else
                myMap.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--;
            else
                count++;
        }
        return ret;
    }
    // 方法四：位操作1
    public 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;
    }
    // 方法四：位操作2
    public 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 { 
    @Test
    public 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]));
    }
}