LeetCode OJ 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.
【思路1】java HashMap
我们用java的HashMap,把数组中的值做为键,把元素的数目作为值。如果出现了一个元素的数目大于nums.length/2,则返回该值。代码如下:
public class Solution {
public int majorityElement(int[] nums) {
if(nums.length==0 || nums==null) return 0;
Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++){
if(map.containsKey(nums[i])){
if(map.get(nums[i])+1 > nums.length/2) return nums[i];
map.put(nums[i], map.get(nums[i])+1);
}
else
map.put(nums[i], 1);
}
return nums[0];
}
}
【思路2】
由于数组中肯定存在一个majority number。因此我们可以遍历数组,如果找到一对值不同的元素就把他们删除,那么最后剩下的一定majority number。这种算法叫Moore’s Voting Algorithm,由Robert S.Boyer 和J Strother Moore于1980年发明,是线性时间复杂度。
举个例子:[1,2,3,1,1,1] (1,2)是一对不相同的元素,(3,1)是另一对不相同的元素,那么剩下的1肯定是majority number。代码如下:
public class Solution {
public int majorityElement(int[] nums) {
if(nums.length==0 || nums==null) return 0;
int count = 0;
int result = 0; for(int i = 0; i < nums.length; i++){
if(count == 0){
result = nums[i];
count = 1;
}
else{
if(nums[i] == result){
count ++;
}
else count --;
}
}
return result;
}
}
当然,这种算法对于存在主元素的数组是有效的,如: A A A C C B B C C C B C C
它肯定能返回主元素C。但是,如果不存在主元素,那么得到的结果就跟遍历顺序有关了。如: A A A C C C B
如果是从左到右,那么结果是B,如果是从右到左,那么结果是A。
最新文章
- JAVA基础知识之网络编程——-网络基础(Java的http get和post请求,多线程下载)
- js自运行函数
- 关于Eclipse的常用快捷键
- Hadoop学习记录(4)|MapReduce原理|API操作使用
- Opencart 之 Registry 类详解
- Core第三方开源Web框架
- python手记(41)
- Chapter 1 Mr.Sherlock Holmes
- struts和struts2的区别
- I/O操作之文件压缩与解压
- 调用sed命令的三种方式
- mybatis设置callSettersOnNulls解决返回字段不全的问题
- 快速EDAS字体嵌入问题
- CSS Modules In Webpack
- mysql innodb 唯一键里的字段为什么不能为NULL
- 基于Hadoop2.7.3集群数据仓库Hive1.2.2的部署及使用
- php -- 类对象调用静态方法
- soapUI&#160;再谈SoapUI接口测试--文件组织与接口“布局”管理
- 安装node
- React Native 常用插件案例