找一个数组中的主元素

问题：在一个规模为N的数组array[N]中，所谓主元素就是出现次数大于N/2的元素，例如 

                                           3.3.4.2.4.4.2.4.4  有一个主元素为4。

          给出一个算法，如果过半元素存在，就找出来，否则给出报告，要求给出O(N)的算法。

 

 

常规想法

 

(1) 穷举：找出元素中每一个数在数据中的数量。时间复杂度O(N^2)

(2) 排序：先对数组快排，然后重头开始遍历一遍计算每个数的数量。时间复杂度O(N*logN+N)

 

经典算法    裁剪数组算法, 时间复杂度为O(2N ) 

     思想： 如果一个数组array[N]，其中有两个元素e1和e2。

      (1) e1不等于e2

      假如e1是数组array[N]的主元素，e2不是。那么e1在array[N]中的数量en>N/2。此时去掉array[N]中的e1和e2两个元素(e1!=e2)。那么新数组array[N-2]中e1的数量为en-1，并且en-1>N/2-1=(N-2)/2。即e1还是新数组array[N-2]的主元素。

      假如e1和e2都不是数组array[N]的主元素，那么去掉e1、e2以后。那么新数组的大小将变成N-2。此时很有可能出现一个新数组的主元素X，此主元素X的数量正好等于X=(N-2)/2+1。但是该主元素就不是原数组的主元素了，因为X= (N-2)/2+1=N/2。那么这样的主元素X我们叫做伪主元素。因此需要通过和裁剪掉元素比较，来确定是否是真正的主元素。

      (2) e1等于e2

      这种情况下不能进行裁剪。只能继续找不同的两个数裁减掉

 

#include<stdio.h>  
#include<malloc.h>
 // 算法源代码，裁剪当前数组中相邻的不同元素  
 void main(){  
    int pArr[6]={4,4,4,4,6,6};  
    int arrLength=6;  //数组长度
    int element=pArr[0];  
    int value=1;  //记录剪裁过程中遇到相同元素的个数
    int delNum=0; //记录裁剪数组的元素个数
	int *dArr=(int *)malloc(arrLength*sizeof(int)); //记录被剪裁的数组元素
	int dTop=0; //当前剪裁数组的索引位置
     
    for(int i=1;i<arrLength;i++){  
       if(value==0){  
           element=pArr[i];  
       }  
       if(pArr[i]==element) //如果当前数组相邻的元素相等  
           value++;  
       else if(value>0){//如果当前数组相邻的元素不等，则需要裁剪得到新的数组  
		   dArr[dTop++]=element;
		   dArr[dTop++]=pArr[i];
           delNum+=2;  
           value--;  
       }  
    }  
	//如果裁剪之后出现了主元素，那么这个主元素有可能是个伪主元素
    if(value>(arrLength-delNum)/2){
		//与裁剪掉的数组元素一一比较
		for(int j=0;j<delNum;j++)
			if(element==dArr[j]) value++;			
		//确定真正的主元素
		if(value>arrLength/2)
			printf("主元素为:%d\n",element);  
    }  

 

 

 

 

评论

4 楼 blackdog1987 2012-08-16  

二分法  二分法相当强大啊。。。各种强大

3 楼 pcdevelop 2010-06-02  

不客气，这个算法的数学道理很简单，但是很牛！

2 楼 Heart.X.Raid 2010-06-02  

谢谢pcdevelop，确实算法有问题：

主要是假如e1和e2都不是主元素，那么去掉之后，数组长度变小，这个时候后面就可能出现一个伪主元素。你的例子“0,1,3,4,6,6”很好，去掉0,1和3,4之后6就成为了伪主元素。

我修改了上面的算法，裁剪过程中记录下裁剪掉的元素。在将找到的那个准主元素与裁剪掉的每一个元素比较一次，相等的时候让value++；

这样最后用value>arrLength/2来确定是否是真正的主元素，而并非伪主元素。

再次感谢你的提醒。确实是我太大意了。

1 楼 pcdevelop 2010-06-01  

如果数组为：0,1,3,4,6,6，将会打印6为数组主元素；
如果数组为：6，0,1,3,4,6，将不会打印任何主元素，即不存在；