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。

最新文章

  1. JAVA基础知识之网络编程——-网络基础(Java的http get和post请求,多线程下载)
  2. js自运行函数
  3. 关于Eclipse的常用快捷键
  4. Hadoop学习记录(4)|MapReduce原理|API操作使用
  5. Opencart 之 Registry 类详解
  6. Core第三方开源Web框架
  7. python手记(41)
  8. Chapter 1 Mr.Sherlock Holmes
  9. struts和struts2的区别
  10. I/O操作之文件压缩与解压
  11. 调用sed命令的三种方式
  12. mybatis设置callSettersOnNulls解决返回字段不全的问题
  13. 快速EDAS字体嵌入问题
  14. CSS Modules In Webpack
  15. mysql innodb 唯一键里的字段为什么不能为NULL
  16. 基于Hadoop2.7.3集群数据仓库Hive1.2.2的部署及使用
  17. php -- 类对象调用静态方法
  18. soapUI&#160;再谈SoapUI接口测试--文件组织与接口“布局”管理
  19. 安装node
  20. React Native 常用插件案例

热门文章

  1. 各类数据库url
  2. sphinx cmd command
  3. ModelState.IsValid一直为false的原因
  4. Vim/gvim容易忘记的快捷键
  5. 【for陷阱】遍历的同时删除元素
  6. tcp协议栈
  7. robotium如何定位控件?
  8. percentiles of live data capture
  9. 转:jquery的live和on
  10. net之session漫谈及分布式session解决方案