X

曜彤.手记

随手写写,关于互联网技术、产品与创业

LeetCode 每日一题 - 169. Majority Element


LeetCode 每日一题系列,今天第五题。昨天由于事情比较多所以没有抽出时间更新文章,今天来一道简单的题,在星期六的日子里轻松一下。建议先看原题的链接自己做一下,然后再参考本文给出的分析与解答进行总结。【Divide and Conquer】【Array】【Bit Manipulation】

169. 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:

Given nums = [2, 7, 2, 15, 2, 7, 2],

Because integer 2 appears more than 3.5 times, so after your function it should return integer 2.

1. 利用HashMap:

相信经过前面几道题目的经验加成,这里大家第一个想到的就是利用 HashMap 来存储每个元素出现的次数。并且使用优化过的 HashMap 流程,即不需要将所有元素的个数全部统计出来后再判断,而是每次循环时先检查 HashMap 里是否含有当前元素,如果有则判断当前元素出现的次数(即 HashMap 中该元素所对应的 Value)是否超过数组长度的一半,如果超过则返回,否则 HashMap 里该元素的 Value 值加一。代码时间复杂度 “O(n)”。代码如下所示:

public static int majorityElement(int[] nums) {
    if (nums.length == 0)  // 如果数组长度为0则返回-1;
        return -1;

    int arrLen = nums.length;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0;i < arrLen; i++) {
        int currentVal = 0;
        if (map.containsKey(nums[i]))  // 如果 HashMap 中存在该值对应的元素则使用该值;
            currentVal = map.get(nums[i]);

        if (currentVal > arrLen / 2) {  // 如果满足条件则返回该元素;
            return nums[i];
        } else {
            map.put(nums[i], currentVal + 1);  // 否则对应元素值加一;
        }
    }

    return -1;
}

2. 优化的方法,堆排序:

如果仔细阅读题目可以发现题目中已经假定数组一定为非空数组,并且一定含有一系列元素的值满足所给条件,即该值对应元素在数组中出现的次数大于数组长度的一半。这里我们便可以采用先排序后取值的方法,如果一个元素满足上述所给条件,则排序后的数组的中间(Middle)元素一定为所求元素。这里我们直接使用 Java 自带的堆排序方法进行排序。代码如下所示:

public static boolean majorityElementOptimize(int[] nums) {
    if (nums.length == 0)
        return -1;

    int arrLen = nums.length;
    Arrays.sort(nums);  // 对数组进行堆排序;
    return nums[arrLen / 2];  // 返回中间元素;
}

3、另一种思路

网友 “JD” 给出的另一种思路,Majority 的元素总量会占到数组一半以上,所以不同数字两两相抵之后 Majority 元素的剩余数量一定大于0。代码如下所示:

public static int majorityElementOptimize(int[] nums) {
    if (nums.length == 0)
        return -1;

    int arrLen = nums.length;
    int mark = nums[0], count = 1;
    for (int i = 1; i < arrLen; i++) {
        if (count == 0) {
            mark = nums[i];
            count = 1;
            continue;
        }

        if (nums[i] != mark) {
            count--;
        }

        if (nums[i] == mark) {
            count++;
        }
    }

    return mark;
}


这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)