主元素问题(Java)

时间:2021-02-06 14:52:48

x称为一个长度为n的数组的a的主元素,如果这个数组里面等于x的元素的数目不少于n/2个。

例如,a={2,3,2,2,5,3,2,4,2},x=2就是这个主元素。给定包含n个元素的数组a,主元素问题就是判断数组a是否包含一个主元素x。

三个方法实现:

方法一:

求中文书,主元素可定是中位数,否则该元素数量少于n/2则不是主元素;快速排序,然后确定中位数时间复杂度O(nlogn)

方法二:

分子思想:

若T中存在主元素,则将T分为两个部分,T的主元素也必为两部分中至少一部分的主元素,因此可用分治法。

将主元素划分为两部分,递归地检查两部分有无主元素。算法如下:

a.若T只含有一个元素,则吃元素就是主元素,返回此数。

b.讲T分为两部分T1和T2(两者元素个数相等或者差一),分别使用递归方法求其主元素m1和m2.

c.若m1和m2都存在且相等,则这个数就是T的主元素,返回此数。

d.若m1和m2都存在且不相等,则分别检查者两个数是否为T的主元素,若有,则返回此数,若无则返回空值。

e.若m1和m2只有一个存在,则检查这个数是否为T的主元素,若是则返回此数,若否就返回空值。

f.若m1和m2都不存在,则T无主元素,返回空值。

方法三:

思路比较新颖,原理是如果一个元素中存在一个主元素(个数大余n/2),则同时删除两个不相等的数,这个主元素不会改变。

简单的说就是一个大小为n的数组中存在一个元素的个数大余n/2,则如果用这个数组中其他的数和该主元素进行抵消的话,最后剩下的一定是主元素,因为主元素个数最多。

该方法可以在O(n)时间内找到主元素。十分高效。

方法一代码:

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = {2,3,2,2,5,3,2,4,2};
        int i = 0;
        Arrays.sort(a);
        int index = a.length/2;
        if(a[0]==a[index]||a[a.length-1]==a[index]){
            System.out.println(a[index]);
        }
    }
}

方法二代码:

方法三代码:

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = {3,5,4,3,3,3,2,3,2};
        int mainE = mainElement(a, 9);
        System.out.println(mainE);
    }
    public static int mainElement(int[]num,int n){
        int seed = num[0];
        int count = 1;
        int i = 0;
        //取出主元素
        for(i = 1; i<n;i++){
            if(seed==num[i]){
                count++;
            }else{
                if(count>0){
                    count--;
                }else{
                    seed = num[i];
                }
            }
        }
        //判断取出的主元素是不是主元素
        count = 0;
        for(i = 0;i<n;i++){
            if(num[i] == seed){
                count++;
            }
        }
        if(count >= n/2){
            return seed;
        }
        return 0;
    }

}