主元素问题（蒙特卡罗方法）笔记

主元素问题

随机输入一个具有n个元素的数组。 要求利用随机化方法输出数组的主元素。

设T[1:n]是一个含有n个元素的数组。当元素x在T中出现次数多于n/2时，称元素x是数组T的主元素。

蒙特卡罗方法。

代码

import java.util.Random;
import java.util.Scanner;

class Main{
    static char x;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        char[] T=new char[n+1];
        for (int i = 1; i <= n; i++) {
            T[i]=sc.next().charAt(0);
        }
        majorityMC(T,n,30);
    }
    public static boolean majority1(char[] T,int n){
        Random r=new Random();
        int i= r.nextInt(n)+1;
        x=T[i];
        int k=0;
        for (i = 1; i <= n; i++) {
            if(T[i]==x)
                k++;
        }
        return k>n/2;
    }
    public static Boolean majorityMC( char[] T, int n, int k){
        for (int i = 1; i <= k; i++) {
            if(majority1(T, n)){
                System.out.println("主元素是"+x);
                return true;
            }
        }
        return false;
    }
}

majorityMC中的k参数表示k次随机。

总结

1次majority1可能找不到主元素（虽然找到主元素的概率以及超过50%），所以需要多次（k次）。

k值设置的越大越准确，因为设一次就找到的概率为p，随机的次数越多，找不到的概率越小，为(1-p) k。找到的概率越大，为1-(1-p) k。

实际运行大概还没到第k次就返回真true，程序结束，不是设k次就一定运行k次。