【LeeCode】169. 多数元素

【题目描述】

​​https://leetcode.cn/problems/majority-element/description/?favorite=2cktkvj​​

给定一个大小为 ​​n​​ 的数组 ​​nums​​ ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ​​⌊ n/2 ⌋​​ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

【示例】

【代码】

package com.company;
import java.util.*;

/**
 * https://leetcode.cn/problems/majority-element/?favorite=2cktkvj
 */

public class threeSum {
    public static void main(String[] args) {
       int[] arr = {2,2,1,1,1,2,2};
       int[] arr1 = {3,2,3};
       majorityElement(arr);
       majorityElement(arr1);


    }
    public static int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
           map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        int num = nums.length / 2;
        List<Integer> list = new ArrayList<>();

        for (Map.Entry<Integer, Integer> ent : map.entrySet()) {
            if(ent.getValue() > num){
                list.add(ent.getKey());
            }
        }
        // 按题目的意思, 应该这个值只有1个
        return list.get(0);
    }
}

【代码2】

​​学习参考​​

数组统计字符数量

// 统计数量
Arrays.stream(arr).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

// 除法 （除以2）
a.length >> 1

package com.company;
import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * Arrays.stream(arr).boxed()
 *       .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
 */

public class threeSum {
    public static void main(String[] args) {
       int[] arr = {2,2,1,1,1,2,2};  // 2
       int[] arr1 = {3,2,3};         // 3
       majorityElement(arr);
       majorityElement(arr1);
    }
    public static int majorityElement(int[] nums) {
        Map<Integer, Long> collect = Arrays.stream(nums).boxed()
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        int size = collect.size() >> 1;
        for (Map.Entry<Integer, Long> entry : collect.entrySet()) {
            if(entry.getValue() > size){
                return entry.getKey();
            }
        }
        return -1;
    }
}

【代码3】

package com.company;
import java.util.*;

public class threeSum {
    public static void main(String[] args) {
       int[] arr = {2,2,1,1,1,2,2};  // 2
       int[] arr1 = {3,2,3};         // 3
       majorityElement(arr);
       majorityElement(arr1);
    }
    public static int majorityElement(int[] nums) {
        int size = nums.length >> 2 ;
        Map<Integer, Integer> map = new HashMap<>(size);

        for(int num: nums){
            // map.merge(num, 1, Integer::sum);
            map.merge(num, 1, (x, y) -> x + y);
        }

        for (Map.Entry<Integer, Integer> en : map.entrySet()) {
            if(en.getValue() > size){
                return en.getValue();
            }
        }
        return -1;
    }
}

【代码4】