LeetCode 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. Credits:Special thanks to @ts for adding this problem and creating all test cases. Subscribe to see which companies asked this question.

题目

给定一个整型数组,找出主元素,它在数组中的出现次数严格大于数组元素个数的二分之一。

样例 给出数组[1,1,1,1,2,2,2],返回 1

分析

方法一 voting,最重要的一个方法

较为简单,遍历一遍记录次数就可以了。 这种方法的思想是把 majority element 看成是 1,而把其他的元素看成是 -1。算法首先取第一个元素 x 作为 majority element,并计 mark = 1;而后遍历所有的元素,如果元素和 x 相等, 则 mark ++;否则如果不等, 则 mark--, 如果 mark == 0, 则重置 mark = 1, 并且更新 x 为当前元素。 由于majority element 的数量大于一半,所以最后剩下的必然是majority element.

代码

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0, candidate = -1;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else if (candidate == nums[i]) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

Paste_Image.png

方法二 排序法

最短的方法,两行代码搞定,因为主元素一定超过一半的元素,所以将数组排序,中间元素一定是主元素

// Sorting
public int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}

方法三

利用hashMap,记录元素的值,和出现的次数

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏黑泽君的专栏

Java集合学习总结

18430
来自专栏Danny的专栏

Java基础——Map接口

  通常来说,Map是一个由键值对组成的数据结构,且在集合中每个键是唯一的。下面就以K和V来代表键和值,来说明一下java中关于Map的几个问题。

12220
来自专栏老马说编程

(54) 剖析Collections - 设计模式 / 计算机程序的思维逻辑

上节我们提到,类Collections中大概有两类功能,第一类是对容器接口对象进行操作,第二类是返回一个容器接口对象,上节我们介绍了第一类,本节我们介绍第二类。...

26190
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 探寻OC对象的本质

42250
来自专栏Python爱好者

Java基础笔记14

12730
来自专栏Golang语言社区

【Go 语言社区】Golang 动态实例化结构体

但这里有一个限制:这个 map 仅仅可以用原型是“func()”的没有输入参数或返回值的函数。 如果想要用这个方法实现调用不同函数原型的函数,需要用到 inte...

440120
来自专栏Coding迪斯尼

面试算法:在未知长度的排序数组中进行快速查找

11920
来自专栏小古哥的博客园

读书笔记-JavaScript面向对象编程(二)

第5章 原型 5.1 原型属性(所有函数拥有一个prototype属性,默认为空对象)   5.1.1 利用原型添加方法和属性 function Gadget(...

45280
来自专栏C语言及其他语言

【每日一题】 1673: 算法2-1:集合union

16610
来自专栏java初学

13.2 具体的集合

28390

扫码关注云+社区

领取腾讯云代金券