首页 > 代码库 > Majority Element
Majority Element
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.
这道题我没有看提示，直接用hash表，遍历数组，将出现的次数保存到hash表中，最后遍历hash表，找出满足要求的元素。时间复杂度为O(n)
1 import java.util.Hashtable; 2 import java.util.Iterator; 3 4 public class Solution { 5 public int majorityElement(int[] num) { 6 Hashtable<Integer, Integer> hashtable = new Hashtable<Integer, Integer>(); 7 int result = 0; 8 9 for(int i = 0; i < num.length; i++){10 Integer times = hashtable.get(num[i]);11 if(times == null)12 hashtable.put(num[i], 1);13 else{14 times = times + 1;15 hashtable.put(num[i], times);16 }17 }//for18 //遍历hash表19 Iterator<Integer> it = hashtable.keySet().iterator();20 while(it.hasNext()){21 int key = it.next();22 if(hashtable.get(key) > num.length / 2){23 result = key;24 break;25 }26 }27 28 return result;29 }30 }
Majority Element
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。