leetcode - [169] Majority Element

2020/02/15

题目描述

Given an array of size n, find the majority element.
The majority element is the element that appears more than ⌊ n/2 ⌋ times.

找出数组中出现次数最多的元素,出现次数处于n/2

举个例子:

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

Update at 2020_0624

重新梳理一下循环中的逻辑:

如果cnt == 0,则令ans等于当前元素,并使cnt = 1,注意,这次遍历就结束了!

否则,如果ans等于当前元素,则cnt++

否则,cnt--

来看下实现:

class Solution {
    public int majorityElement(int[] nums) {

        int len = nums.length;
        int ans = nums[0];
        int cnt = 1;

        for (int i = 1; i < len; i++){
            if (cnt == 0){
                ans = nums[i];
                cnt = 1;
                continue;
            }
            if (nums[i] == ans){
                cnt++;
            } else {
                cnt--;
            }
        }
        return ans;
    }
}

解法1

我的理解是这样的:

首先,创建一个HashMap<Integer, Integer>,然后遍历数组,统计每个元素出现的次数。

接着,遍历Map,从中找出value最大的元素。

@Test
public void question169(){
    int[] nums = {3, 2, 3};

    // Step1: Build HashMap.
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int num: nums){
        if (map.get(num) != null){
            map.put(num, map.get(num) + 1);
        } else {
            map.put(num, 1);
        }
    }
    
    // Step2: Find the majority element.
    int result = 0;
    int count  = 0;
    for (Map.Entry<Integer, Integer> entry: map.entrySet()){
        if (entry.getValue() > count){
            count  = entry.getValue();
            result = entry.getKey();
        }
    }
}

优化1

上面的解法有个很严重的缺点:做了很多不必要的计算!

一旦能获得想要的结果,之后的计算都是不必要的。

因此,在构建Map时,一旦发现某个元素出现的次数大于n/2,就可以结束了。

@Test
public void improve169UsingHashMap(){

    int ret = 0;
    int[] nums = {3, 2, 3, 2, 3, 1, 3, 8, 3};
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int num: nums){
        if (!map.containsKey(num)){
            map.put(num, 1);
        } else {
            map.put(num, map.get(num) + 1);
        }
        // Must be >, eg: [2, 2, 1, 1, 1, 2, 2]
        if (map.get(num) > nums.length / 2){
            ret = num;
            break;
        }
    }
    System.out.println(ret);
}

Update at 2020_0527

代码优化:

class Solution {
    public int majorityElement(int[] nums) {
        int len = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int n: nums){
            int cur = map.getOrDefault(n, 0) + 1;
            if (cur > (len >> 1)){
                return n;
            }
            map.put(n, cur);
        }
        return -1;
    }
}

解法2

在讨论区看到一种惊艳的做法,被称之为AC,具体流程如下:

@Test
public void improve169UsingAC(){
    int[] nums = {3, 2, 1, 3, 3, 1, 3, 8, 3};

    int n = nums.length, m = nums[0], c = 1;
    for (int i = 1; i < n; i++){
        if (nums[i] == m){
            c++;
        } else if (c > 0){
            c--;
        } else {
            m = nums[i];
            c = 1;
        }
    }

    System.out.println("m = " + m);
}

Update at 2020_0527

时隔三个月,对最后一种解法仍感到惊艳。

回过头来,再来总结一番:

首先,假设第一个元素就是重复次数最多的元素,并设置fre = 1

然后,从第二个元素开始遍历,若当前元素与首元素相等,则fre++

否则判断fre > 0,若是,fre--,否则,假定当前元素为结果,并重新设置fre = 1

来看下调整后的示意图:

再来看下实现:

class Solution {
    public int majorityElement(int[] nums) {
        int len = nums.length;
        int ans = nums[0], fre = 1;

        for (int i = 1; i < len; i++){
            if (nums[i] == ans){
                fre++;
            } else if (fre > 0){
                fre--;
            } else {
                ans = nums[i];
                fre = 1;
            }
        }
        return ans;
    }
}

Enjoy it !

Reference


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory