当前位置：首页 > news >正文

算法面试题:多数元素

news 来源：原创 2024/4/30 16:15:12

leetcode 面试题目：

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

方案一：map 统计查询

  /**
     * map 统计查询
     * 执行用时 : 22 ms
     * 内存消耗 :47.3 MB
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {

        int ret = -1;
        if(nums.length <= 2){
            return nums[0];
        }
        int count = nums.length/2;
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++){
            if (!map.containsKey(nums[i])){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],map.get(nums[i])+1);
            }
        }

        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            int mapKey = entry.getKey();
            int mapValue = entry.getValue();
            if (mapValue> count){
                ret = mapKey;
                break;
            }
        }

        return ret;
    }

方案二单次循环计数

   /**
     * 单次循环 计数
     * 执行用时 :2 ms
     * 内存消耗 :41.6 MB
     * @param nums
     * @return
     */
    public static int majorityElement2(int[] nums) {

        int ret = nums[0];
        int cnt = 1;
        for (int i = 1; i < nums.length; i++) {
            if (ret == nums[i]) {
                cnt++;
            } else {
                cnt--;
                if (0 == cnt) {
                    ret = nums[i];
                    cnt = 1;
                }
            }
        }

        return ret;
    }

方案三使用自带的排序

    /**
     * 使用自带的排序
     * 执行用时 :2 ms
     * 内存消耗 :42.2 MB
     * @param nums
     * @return
     */
    public static int majorityElement3(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }