java 找数组中的多数元素

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;
    }
}