[数据结构与算法]Java---数组---多数元素

? ? ? 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ? n/2 ? 的元素。

对于数组中的多数元素,本文章列举三种求法:

1.排序法

? ? ? ? 因为数组中的多数元素的数量是大于数组长度的一半的,所以将数组排序后,对于长度为奇数的数组,最中间的那个数一定是数组中的多数元素;而对于长度为偶数的数组来说,最中间的数有两个,而这两个数一定都为多数元素.

eg:

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = {7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 7, 7, 7, 7};
        manyNumSort(arr);
    }
    public static void manyNumSort(int[] arr) {
//先进行排序,直接调用Arrays.soet方法快速排序
        Arrays.sort(arr);
//排序完成后直接输出最中间的数
        System.out.println(arr[arr.length / 2]);
    }
}

2.分治法

? ? ? ?分治法的思想就是将一个大数组从中间分为两个子数组,再分别求这两个子数组的多数元素,如果两个子数组的多数元素相同,则原来大数组的多数元素就为子数组的多数元素;如果两个多数元素不相同,则再次遍历两个子数组,找出那个出现次数最多的那个元素,并返回.

eg:

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = {7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 7, 7, 7, 7};
        manyNumRecursion(arr);
        int num = manyNumRecursion(arr);
        System.out.println(num);
    }
    public static int manyNumRecursion(int[] arr) {
        return manyNumRecursionInternal(arr,0,arr.length - 1);
    }

    public static int manyNumRecursionInternal(int[] arr, int left, int right) {
        if(left == right){
            return arr[left];
        }
        int mid = (left + right)/2;
        int leftNum = manyNumRecursionInternal(arr,left,mid);
        int rightNum = manyNumRecursionInternal(arr,mid+1,right);
        if(leftNum == rightNum){
            return leftNum;
        }
        int leftCount = arrCount(arr,leftNum);
        int rightCount = arrCount(arr,rightNum);
        return leftCount > rightCount ? leftNum :rightNum;
    }
    public static int arrCount(int[] arr,int value){
        int count = 0;
        for(int i : arr){
            if(i == value){
                count++;
            }
        }
        return count;
    }
}

3.投票法

? ? ? ?投票法的思路类似于现实中的候选人选举,但是对于这个问题来说必须有一个候选人的票数超过总票数的一半才可以当选(也就是数组中的多数元素),可能有多个候选人,但是对于每个候选人来说,只有两种情况,把票投给你和把票投给别人.

? ? ? ?所以投票法的解决方法就是有投给你的票,总票数加1,不是投给你的票,总票数减1.当一个候选人的票数为0时,更换下一个候选人,当最后有一个候选人的票数>0,则这个候选人选举成功(即多数元素).

eg:

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = {7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 7, 7, 7, 7};
        int manyNum = manyNumVote(arr);
        System.out.println(manyNum);
    }

    public static int manyNumVote(int[] arr) {
        int count = 0;
        Integer candidate = null;
        for(int i : arr){
            if(count == 0){
                candidate = i;
            }
            if(i != candidate){
                count--;
            }else{
                count++;
            }
        }
        return candidate;
    }
}