169.多数元素

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n/2⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
题目链接

思路

HashMap
使用哈希表统计每个元素出现的次数，返回哈希表中值最大的键。
排序
如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 ⌊n/2⌋ 的元素（下标从 0 开始）一定是众数。
因此，对数组进行排序并返回下标为⌊n/2⌋的数组元素。
随机化
因为超过 ⌊n/2⌋ 的数组下标被众数占据了，这样我们随机挑选一个下标对应的元素并验证，有很大的概率能找到众数。
分治
如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。
我们使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。

Boyer-Moore投票算法
如果我们把众数记为 +1+1+1，把其他数记为 −1-1−1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

代码(java版本)

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;

public class MajorityElement {

 private int randRange(Random rand, int min, int max){
     return rand.nextInt(max - min) + min;
 }
 
 private int countOccurences(int[] nums, int num){
     int count = 0;
     
     for(int num1 : nums){
         if(num == num1){
             count++;
         }
     }
     
     return count;
 }
 
 public int majorityElement(int[] nums){
     Random rand = new Random();
     
     int majorityCount = nums.length / 2;
     
     while(true){
         int candidate = nums[randRange(rand, 0, nums.length)];
         if(countOccurences(nums, candidate) > majorityCount){
             return candidate;
         }
     }
 }
 
 private int countInRange(int[] nums, int num, int lo, int hi){
     int count = 0;
     for(int i = lo; i <= hi; i++){
         if(nums[i] == num){
             count++;
         }
     }
     return count;
 }
 
 private int majorityElementRec(int[] nums, int lo, int hi){
     if(lo == hi){
         return nums[lo];
     }
     
     int mid = (hi - lo) / 2 + lo;
     int left = majorityElementRec(nums, lo, mid);
     int right = majorityElementRec(nums, mid + 1, hi);
     
     if(left == right){
         return left;
     }
     
     int leftCount = countInRange(nums, left, lo, hi);
     int rightCount = countInRange(nums, right, lo, hi);
     
     return leftCount > rightCount ? left : right;
 }
 
 //方法4：分治
 public int majorityElement1(int[] nums){
     return majorityElementRec(nums, 0, nums.length - 1);
 }
 
 //方法5：Boyer-Moore
 public int majorityElement2(int[] nums){
     int count = 0;
     Integer candidate = null;
     
     for (int num : nums){
         if(count == 0){
             candidate = num;
         }
         count += (num == candidate) ? 1 : -1;
     }
     
     return candidate;
 }
 
 public static void main(String[] args) {
     int[] nums = new int[]{2,2,1,1,1,2,2};
     
     //方法1：HashMap

// Map<String,Integer> map = new HashMap<>();
// for(Integer num : nums){
// String tempNum = num.toString();
// if(!map.keySet().contains(tempNum)){
// map.put(tempNum, 1);
//
// }else{
// map.put(tempNum, map.get(tempNum) + 1);
// }
// }
//
// Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
// for(;iterator.hasNext();){
// Entry<String, Integer> next = iterator.next();
// String key = next.getKey();
// Integer value = next.getValue();
// if(value > (int)(nums.length / 2)){
// System.out.println(key);
// }
// }

     //方法2：排序

// Arrays.sort(nums);
// System.out.println(nums[nums.length / 2]);

     //方法3：随机化
     MajorityElement majorityElement = new MajorityElement();
     int majority1 = majorityElement.majorityElement(nums);
     System.out.println(majority1);
     
     //方法4：分治
     int majority2 = majorityElement.majorityElement1(nums);
     System.out.println(majority2);
     
     //方法5：Boyer-Moore投票算法
     int majority3 = majorityElement.majorityElement2(nums);
     System.out.println(majority3);
 }

}

victory的博客

leetcode | 169.多数元素

169.多数元素

题目描述

思路

代码(java版本)