## 主元素 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.

①我首先想到了将数组排序，然后记录每一个数值出现的次数，满足大于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中建议了很多解法：

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

### 叶枫啦啦

LeetCode--Majority Element--Boyer-Moore算法总结

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

6
0
DDD(五)

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

MrYuZixian

6
0

6
0

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

HelloDeveloper

7
0

10
0