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