友链
姚屹晨

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