java 找数组中的多数元素

java 找数组中的多数元素,第1张

java 找数组中的多数元素 题目:给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。(⌊  ⌋ 指向下取整)

目录

方法一:排序法

思想:

代码实现:

方法二:分治法

思想:

分析:


方法一:排序法 思想

因为多数元素出现的次数是大于⌊ n/2 ⌋的,所以在进行排序后的数,中位数一定是多数元素

代码实现
import java.util.Arrays;
import java.util.Scanner;

public class shuzuMost {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入元素个数");
        int n = scan.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scan.nextInt();
        }
        if(arr.length == 1)
            System.out.println(arr[0]);
        Arrays.sort(arr);
        System.out.println(arr[arr.length/2]);
    }
}
方法二:分治法 思想

众数一定>n / 2,所以将一个数组拆分为两部分后,众数一定至少存在在一个子区间中。

分析

原问题:在一个数组中找到众数

子问题:在左半区间找到左边的众数left  在右半区间找到右边的众数right

若左区间得出的众数等于右区间得出的数,则说明此数一定是众数

eg: [2,2,2,2,2,1]   

left ==right   

return left或right 

若左右区间得出的数字不同,则算出每个数字在数组中出现的次数,最多的那个数就是众数

eg:[2,2,2,2,1,1,1]

left != right

left > right         return left

left < right       return right

方法二的循环次数小于方法一,效率更高。

代码实现
import java.util.Arrays;

public class shuzuMost {
    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        int num = manyNumRecursion(nums);
        System.out.println(num);
    }

    public static int manyNumRecursion(int[] nums) {
        return manyNumRecursionInternal(nums, 0, nums.length - 1);
    }
//传入一个数组,将大的区间分为左右子区间,分别计算左右区间的众数
    public static int manyNumRecursionInternal(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = (left + right) >> 1;
        int leftNum = manyNumRecursionInternal(nums, left, mid);
        int rightNum = manyNumRecursionInternal(nums, mid + 1, right);
        if (leftNum == rightNum) {
            return leftNum;
        }
        int leftCount = numCount(nums, leftNum);
        int rightCount = numCount(nums, rightNum);
        return leftCount > rightCount ? leftNum : rightNum;
    }
//分别计算求出左右子区间的count,并返回,大的,就是整个数组的众数
    private static int numCount(int[] nums, int value) {
        int count = 0;
        for (int i : nums) {
            if (i == value) {
                count++;
            }
        }
        return count;
    }
}
方法三:投票法 思想:

赞成的+1,不赞成的-1,若某一个数>0 ,则这个数就是众数

代码实现
public class shuzuMost {
    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        int num = manyNumVote(nums);
        System.out.println(num);
    }
    public static int manyNumVote(int[] nums){
        //记录赞成者人数
        int count = 0;
        Integer candidate = null;
        for(int i : nums){
//            如果只有一个数,则此数就是众数
            if(count == 0){
                candidate = i;
            }
//            不赞成
            if(i != candidate){
                count += -1;
            }else{
                count += 1;
            }
        }
        return candidate;
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5605600.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-15
下一篇 2022-12-15

发表评论

登录后才能评论

评论列表(0条)

保存