For 3 minutes a day, take the algorithmic counterattack route.

Handled in the collection

A daily collection of LeetCode preambles

Code warehouse

Making: github.com/meteor1993/…

Gitee: gitee.com/inwsy/LeetC…

Title: A Daily LeetCode (39) : Most elements

Title source: leetcode-cn.com/problems/ma…

Given an array of size N, find most of the elements. Most elements are those that occur more than ⌊ n/2 ⌋ in the array.

You can assume that the array is non-empty and that a given array always has most elements.

Example 1:

Input: [3,2,3] Output: 3Copy the code

Example 2:

Input: [2,2,1,1, 2,2] Output: 2Copy the code

Solution: Hash table

One of the things I saw in this problem and one of the ideas I had was to put it in a Map, use the current element as the key, and use the frequency of occurrence as the value.

So, whenever a value is greater than half of the array in the loop, we can just return it.

public int majorityElement(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    if (nums.length == 1) return nums[0];
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(nums[i])) {
            map.put(nums[i], map.get(nums[i]) + 1);
            // Return if the current value is greater than half
            if (map.get(nums[i]) > nums.length / 2) {
                returnnums[i]; }}else {
            map.put(nums[i], 1); }}return -1;
}
Copy the code

The violence plan is simple, simple, but the problem is that it’s not efficient.

Solution 2: Sort

The second solution is fairly straightforward: sort the entire array and take half of the positions. Because the mode is greater than half, we can take half of the positions correctly.

public int majorityElement_1(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}
Copy the code

Solution 3: Random number

This scheme is very interesting. We just take a random number and determine whether the mode we get is the mode number, because the mode number will be more than half, so we have a half chance of getting the value we want.

The time it takes to do this depends on the face, and I’m drunk, too.

public int majorityElement_2(int[] nums) {
    int count = nums.length / 2;
    Random rand = new Random();
    while (true) {
        int index = rand.nextInt(nums.length);
        if (countOccurences(nums, nums[index]) > count) {
            returnnums[index]; }}}// count the number of num occurrences
private int countOccurences(int[] nums, int num) {
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        if(nums[i] == num) { count++; }}return count;
}
Copy the code

I have submitted this scheme for several times, and the worst time is 2ms, and the best time is 1ms. I estimate that 0ms May be produced if I submit it several times more.