文档章节

主元素 Majority Element

叶枫啦啦
 叶枫啦啦
发布于 2017/06/06 17:09
字数 605
阅读 15
收藏 0

问题:

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.

解决:

①我首先想到了将数组排序,然后记录每一个数值出现的次数,满足大于N/2的返回即可。耗时6ms。

public class Solution {
    public int majorityElement(int[] nums) {//出现次数大于n/2
        int count = 1; 
        int n = nums.length;
        int majority = 0;
        Arrays.sort(nums);
        if(nums.length == 1) return nums[0];
        for (int i = 1;i < nums.length ;i ++ ) {
            if (nums[i] == nums[i - 1]) {
                count ++;
                if(count > n / 2){
                    majority = nums[i];
                    break;
                }
            }else{
                count = 1;
            }       
        }
        return majority;
    }
}

Moore voting algorithm--每找出两个不同的element,就成对删除即count --,最终剩下的一定就是所求的。时间复杂度:O(n)。耗时3ms。

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

③leetcode中建议了很多解法:

第一种是Brute force solution,时间复杂度为O(n2),顾名思义,遍历数组,依次判断每个元素是否为多数元素。

第二种是Hash table,时间复杂度为O(n),空间复杂度也为(n),对数组中的每个元素计数,大于⌊n/2⌋时即为所求结果。

第三种是Sorting,时间复杂度为O(nlogn),找到第n/2个元素即可。

第四种是Randomization,平均时间复杂度为O(n),最坏情况为无穷大。随机选一个元素,判断其是否为多数元素。由于选中多数元素的概率大于1/2,尝试次数的期望<2。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int size = nums.size();
        while (true) {
            int r = nums[rand() % size];
            int count = 0;
            for (int i = 0; i < size; i++) {
                if (r == nums[i]) {
                    count++;
                }
            }
            if (count > size >> 1) {
                return r;
            }
        }
    }
};

第五种是Divide and conquer,时间复杂度为O(nlogn),将数组分成两半,分别递归查找这两部分的多数元素,若两者相同,则为多数元素,若不同,则其中之一必为多数元素,判断其一即可。

第六种是Moore voting algorithm,时间复杂度为O(n),每找出两个不同的element,就成对删除即count --,最终剩下的一定就是所求的。

© 著作权归作者所有

叶枫啦啦
粉丝 13
博文 583
码字总数 400448
作品 0
海淀
私信 提问
LeetCode--Majority Element--Boyer-Moore算法总结

找数组中的Majority Element,Majority Element的定义见下,对应着LeetCode上的两道题,直接看题: LeetCode--169. Majority Element 给定一个长度为n的数组,找出其中的Majority Element。其...

CLthinking
2018/12/22
0
0
Leetcode PHP题解--D83 169. Majority Element

D83 169. Majority Element 题目链接 169. Majority Element 题目分析 给定一个数组,返回其中出现次数超过一半的元素。 思路 用array_count_values函数计算元素出现次数,用arsort逆序排序结...

skys215
06/09
7
0
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 ......

Leafage_M
2018/01/06
0
0
LeetCode求众数(寻找多数元素/主元素问题)

1、题目描述 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 示例 2: 说明: 此...

hfk
01/10
0
0
LeetCode 169. Majority Element - majority vote algorithm (Java)

1. 题目描述Description Link: https://leetcode.com/problems/majority-element/description/ Given an array of size n, find the majority element. The majority element is the elemen......

rgvb178
2017/12/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
6
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
6
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
昨天
6
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
7
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部