| package cn.edu.xidian.sselab.array; import java.util.Arrays; import java.util.HashMap; import java.util.Map; /** * * @author zhiyong wang * title: Majority Element * content: * 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. * */ public class MajorityElement { //从头开始遍历数组中所有的数，用一个HashMap记录每个数字及数字出现的次数，选出次数大于数组个数一半的数值 public int majorityElement(int[] nums){ int length = nums.length; int result = nums[0]; Map<Integer,Integer> times = new HashMap<Integer,Integer>(); for(int i=0;i<length;i++){ if(times.containsKey(nums[i])){ int time = times.get(nums[i]) + 1; if(time >= length / 2){ result = nums[i]; break; } times.put(nums[i], time); }else{ times.put(nums[i], 0); } } return result; } //从leetcode学习的方法，非常巧妙，调用Arrays自动排序接口，因为搜求结果一定会大于一半，所以中间的数值一定就是所求的值 public int majorityElement1(int[] nums){ Arrays.sort(nums); return nums[nums.length / 2]; } } ? |
原文：http://www.cnblogs.com/wzyxidian/p/5065022.html