【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 = (Integer) entry.getValue(); System.out.println("value:"+value+"key:"+key); if(value>top) return key; } return -1; } }
这样就没有问题了!
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。