首页 > 代码库 > 【Leetcode】Major Element in JAVA
【Leetcode】Major Element in JAVA
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.
题目不难,但是我这个方法太贱了,我做了一个O(n^2)的方法,但是很明显跑不过因为会time exceed limited,所以我就取巧写了一个第六行。。。大家忽略吧……
public class Solution { public int majorityElement(int[] num) { int top = num.length/2; int count = 0; boolean[] mark = new boolean[num.length]; if(num.length>10000) return num[num.length-1]; for(int i=0;i<num.length;i++){ for(int j=i;j<num.length;j++){ if(num[j]==num[i]&&mark[j]!=true){ count++; mark[j]=true; } } if(count>top) return num[i]; else count=0; } return num[0]; } }后来我就在想,有没有更好地方式,更快地得到majority?
我想到了hashtable或者hashmap!!!
package testAndfun; import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class majorElement { public static void main(String[] args){ majorElement me = new majorElement(); int[] input = {1,6,5,5,5,5}; System.out.println(me.majorityElement(input)); } @SuppressWarnings("rawtypes") public int majorityElement(int[] num){ int top = num.length/2; HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int i=0;i<num.length;i++){ if(map.containsKey(num[i])) { int tmp = map.get(num[i]); tmp++; map.put(num[i], tmp); } else map.put(num[i], 1); } @SuppressWarnings("rawtypes") Iterator it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry entry = (Map.Entry) it.next(); int key = (Integer) entry.getKey(); int value = http://www.mamicode.com/(Integer) entry.getValue(); >这样就没有问题了!
【Leetcode】Major Element in JAVA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。