多数元素

package com.memorys.test;
import java.util.HashMap;import java.util.Map;
/** * * 题目来源于： * https://leetcode-cn.com/leetbook/read/top-interview-questions/xm0u83/ * * @Description: * 多数元素 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 * * @Date: 2021-7-29 12:49 * @return */public class Main {
    public static void main(String[] args) {
        int[] arr1 = {2,1,2,3,1,2,2};        int result1 = getMostNum1(arr1);        System.out.println(result1);
        int[] arr2 = {2,1,2,3,1,2,2};        int result2 = getMostNum2(arr2);        System.out.println(result2);
        int[] arr3 = {2,1,2,3,1,2,2};        int result3 = getMostNum3(arr3);        System.out.println(result3);            }


    /**     * @Description: 思路     * 从前往后依次计算每个数字出现的次数，当遇到一个数字出现次数 > n/2 的时候，终止循环，返回对应的数字     * 因为一个数组中最多只能出现啊一个 出现次数 大于 半数的 值     *     * 时间复杂度:O(n)：     * 循环n次，循环内比较1次，循环内 加次数 1次，put 1次，     * 因此操作次数为 n + n + n + n = 4n     *     * 空间复杂度：O(n)：     * 额外用了 一个空间 存储 数组 长度 为 1     * 额外用了一个 Map 存储 字符出现次数 为 n * 2     * 每次循环额外用了一个空间 存储 计算后的出现次数 为 n     * 因此：额外空间使用为 1 + 2n + n = 3n + 1     *     * @Date: 2021-7-30 10:54     * @param arr      * @return int     */    private static int getMostNum1(int[] arr) {        int arrLength = arr.length;        Map<Integer, Integer> resultMap = new HashMap<>();        for (int i = 0; i < arr.length; i++) {            if (!resultMap.containsKey(arr[i])){                resultMap.put(arr[i],1);                continue;            }            int mostNumCount = resultMap.get(arr[i]) + 1;            if (mostNumCount > arrLength/2){                return arr[i];            }            resultMap.put(arr[i],  mostNumCount);        }
        throw new RuntimeException("居然没找到?");    }

    /**     * @Description: 思路     * 位运算。     * 一直以来感觉位运算 都要作为单独的方面去考虑， 通过常规的思路很难想到位运算上。     *     * int 类型 总共 32 位， 计算出 每一位 出现最多的数字， 组成的数字即为 出现最多的数。     * 因为 每一位 只有 0  和 1 两种可能，因此，只得出 1 出现的次数，也就得出了  0 出现的次数。     *     * 每个数字获取每一位的值 需要 32 次     * 循环所有数字需要 n个循环     * 在计算最终结果的时候 依然需要 再次遍历 定义的32长度的数组 需要 32 次     * 因此：时间复杂度O（n） : 32 * n + 32     *     * 记录 每一位 出现的次数，需要 一个 32位的数组     * 记录 当前位 的数字，需要1 个空间     * 记录 除以当前为 剩余部分数字 需要 1 个空间     * 记录 最终计算的结果 需要 1个空间     * 因此空间复杂度：O(1): 32 + 1 + 1 + 1     *     *     * @Date: 2021-8-2 12:23     * @param arr2      * @return int     */    private static int getMostNum2(int[] arr2) {        int [] countArr = new int[32];        int temp;        int surplus;        for (int i = 0; i < arr2.length; i++) {            surplus = arr2[i];            for (int j = 0; j < countArr.length; j++) {                temp = surplus%2;                if (temp == 1){                    countArr[j] += 1;                }                surplus = surplus/2;                if (surplus == 0){                    break;                }            }        }
        int result = 0;        for (int i = 0; i < countArr.length; i++) {            if (countArr[i] > arr2.length/2){                result = (int) (result + Math.pow(2, i));            }        }        return result;    }

    /**     * @Description: 思路：     * 摩尔投票法：     * 不同的数字相互抵消，最终剩余的数字就是我们要的最多的数字。     *     * 如果，不是和最多的数字 进行抵消，那么，最后剩余的肯定是最多的数字     * 如果所有的数字都和 最多的抵消， 那么也没最多的数字多，最后剩余的数字 依然是 最多的哪个数字     *     * 时间复杂度：O(n) = n     * 遍历一次数组  n     *     * 空间复杂度：O(1) = 1 + 1     * 定义一个 保存结果的 int     * 定义一个 保存当前最多的数字 个数 int     *     *     * @Date: 2021-8-2 13:57     * @param arr3     * @return int     */    private static int getMostNum3(int[] arr3) {        int result = 0;        int count = 0;
        for (int i = 0; i < arr3.length; i++) {            if (count== 0){                result = arr3[i];                count ++;            } else if (result == arr3[i]){                count ++;            } else {                count --;            }                    }        if (count > 0){            return result;        }        throw new RuntimeException("居然没找到?");    }

}