LeetCode 169. Majority Element

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 1:

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

Input: [2,2,1,1,1,2,2]
Output: 2

题目大意:求数组中出现的次数超过n/2的数字。

解法一:

O(logn)的时间复杂度。

先对数组进行排序,然后取中间的数字就一定是出现次数大于n/2的数字。

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

好吧,如果写一篇文章就采用这么low逼的答案,估计又有人要喷了。

解法二:

O(n)的时间复杂度,O(n)的空间复杂度。

     public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> hashMap = new HashMap<>(); 
        for (int i = 0;i <nums.length;i++){
            if (hashMap.containsKey(nums[i])){
                hashMap.put(nums[i],hashMap.get(nums[i])+1);
            }else {
                hashMap.put(nums[i],1);
            }
            if (hashMap.get(nums[i])>nums.length/2){
                    return nums[i];
                }
        }
         return -1;
         
    }

解法三:

O(n)的时间复杂度,O(1)的空间复杂度。

思路:数组中有一个数字的出现次数超过一半,也就是说这个数字的出现次数比其他的所有的数字的出现次数之和还要多。因此我们可以考虑遍历数组的时候保存两个值,一个是数组中的数字,一个数次数。当我们遍历到下一个数字的时候,如果下一个数字与我们之前保存的数字是相同的,那么次数加1,不同则减1,。如果次数为0,那么我们需要保存下一个数字,并把次数设置为1,。由于我们要找到的数字比其他的所有的数字的出现次数还要高,那么我们要找的数字一定是最后一次把次数设置为1时候所对应的数字。

public int majorityElement(int[] nums) {
    int count=0, ret = 0;
    for (int num: nums) {

        if (count==0)
            ret = num;
        if (num!=ret)
            count--;
        else
            count++;
    }
    return ret;
}

解法四:

O(n)的时间复杂度。

这是一种采用快速排序中的partition()函数的方法。

后面会补上来

总结:无论从时间复杂度还是空间复杂度还是代码量上,解法三的算法的效率都是最好的。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云霄雨霁

Java--类和对象之句柄、作用域

2646
来自专栏Java爬坑系列

C++中的显式类型转化

  类型转化也许大家并不陌生,int i; float j; j = (float)i; i = (int)j; 像这样的显式转化其实很常见,强制类型转换可能会...

2217
来自专栏Python爬虫实战

Python指南:面向对象程序设计

接下来将基于使用程序对圆进行描述这一问题,来解释纯过程型程序设计方法存在的问题。用于描述一个圆所需要的最少数据包括圆心坐标(x, y)以及圆的半径,简单的方法是...

911
来自专栏Java技术分享

Java 可变参数

Java1.5增加了新特性:可变参数:适用于参数个数不确定,类型确定的情况,java把可变参数当做数组处理。注意:可变参数必须位于最后一项。当可变参数个数多余一...

22010
来自专栏较真的前端

关于数据类型转换的面试题总结

2635
来自专栏程序员互动联盟

【专业技术】关于JS的prototype

概述: 在接触JS的过程中,随着理解的深入会逐渐的理解一些比较深奥的理论或者知识,那么今天我们来介绍一下比较难理解的prototype和constructor。...

3416
来自专栏黑泽君的专栏

java基础学习_基础语法(下)01_day05总结

============================================================================= ==...

971
来自专栏和蔼的张星的图像处理专栏

c++ primer2 变量和基本类型。

这四种初始化方式c++11都是支持的。c++11中用花括号来初始化变量得到了全面应用。

1191
来自专栏程序员互动联盟

【编程基础】Java的八种基本数据类型

程序=数据+算法,也就是说程序就是你编写算法操作数据。Java是一种强类型语言,也就是说每一个变量都必须是某种类型的变量。在Java中数据类型分为基本数据类型和...

3778
来自专栏静默虚空的博客

[Java 基础]控制语句

选择语句 if语句 if语句会判断括号中的条件是否成立,如果成立则执行if语句中的代码块,否则跳过代码块继续执行。 语法 if(布尔表达式) { //如果布尔...

2116

扫码关注云+社区

领取腾讯云代金券