主元素 算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了主元素 算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3302字,纯文字阅读大概需要5分钟。
内容图文
![主元素 算法](/upload/InfoBanner/zyjiaocheng/1066/6e105ccec73849efa725db3bf0768e04.jpg)
问题描述:
设T[0:n-1]是n个元素的数组。对任一元素x,设S(x)={i|T[i]=x}。当|S(x)|>n/2时,称x为T的主元素。设计一个线性时间算法,确定T[0:n-1]是否有一个主元素。
分析与解答:
(1)基于分治法的线性期望时间求主元素算法
中位数:数列排序后位于最中间的那个数,如果一个数列有主元素,那么必然是中位数。求一个数列有没有主元素,只要看中位数是不是主元素。
找中位数的方法:选择一个元素作为划分起点,然后用快速排序的方法将小于它的移动到左边,大于它的移动到右边。这样将元素划分为两个部分。此时,划分元素所在位置为k。如果k>n/2,那么继续用同样的方法在左边部分找;反之,就在右边部分找;k=n/2时,就找到了中位数。
根据快速排序的思想,可以在平均时间复杂度为O(n)的时间找出一个数列的中位数。然后再用O(n)的时间检查它是否为主元素。
代码如下所示。
- #include <iostream>
- using namespace std;
- #define MAXNUM 100
- //基于分治法的线性期望时间求主元素算法
- void Swap(int *a, int *b)
- {
- int tmp = *a;
- *a = *b;
- *b = tmp;
- }
- //随机划分
- int PartitionRandom(int a[], int first, int last)
- {
- int priot = first + rand() % (last - first + 1);
- Swap(&a[first], &a[priot]);
- int key = a[first];
- while(first < last)
- {
- while(first < last && a[last] >= key)
- {
- last--;
- }
- Swap(&a[first], &a[last]);
- while(first < last && a[first] <= key)
- {
- first++;
- }
- Swap(&a[first], &a[last]);
- }
- return first;
- }
- int Select(int a[], int first, int last , int i)
- {
- if(first == last)
- {
- return a[first];
- }
- int priot = PartitionRandom(a, first, last);
- int k = priot - first + 1;
- if(k == i)
- {
- return a[k];
- }
- if(k > i)
- {
- return Select(a, first, priot - 1, i);
- }
- else//k < i
- {
- return Select(a, priot + 1, last, i - k);
- }
- }
- void FindMaster(int a[], int length)
- {
- int mid = length/2;
- int key = Select(a, 0, length - 1, mid);
- cout << "中位数为:" << key << endl;
- int count = 0;
- for(int i = 0; i < length; i++)
- {
- if(a[i] == key)
- {
- count++;
- }
- }
- if(count > mid)
- {
- cout << "主元素为:" << key << endl;
- }
- else
- {
- cout << "该数组中没有主元素" << endl;
- }
- }
- int main(int argc, char* argv[])
- {
- int a[MAXNUM];
- int length;
- cout << "请输入数组元素个数:";
- cin >> length;
- for(int i = 0; i < length; i++)
- {
- cin >> a[i];
- }
- cout << "输入的元素如下所示:" << endl;
- for(int i = 0; i < length; i++)
- {
- cout << a[i] << " ";
- }
- cout << endl;
- FindMaster(a, length);
- return 0;
- }
时间复杂度分析:由于查找中位数的平均复杂度为O(n),然后遍历一次数组,进行判定,时间辅助度为O(n)。所以,总的时间复杂度为O(n)+O(n) = O(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 无主元素,返回空值。
(3)无序集的主元素问题的线性时间算法
这个问题可以采用《编程之美》上“寻找发帖水王”的方法。如果每次删除两个不同的数字(不管是否包含主元素的数字),那么在剩下的数字中,主元素的出现的次数仍然超过总数的一半。可以通过不断的重复这个过程,转化为更小的问题,从而得到答案。
代码如下所示。
- void Find(int a[], int length)
- {
- int candidate;
- int i, ntimes;
- i = 0;
- ntimes = 0;
- for(i = 0; i < length; i++)
- {
- if(ntimes == 0)//计数为0时,读入新的元素,计数加1
- {
- candidate = a[i];
- ntimes = 1;
- }
- else
- {
- if(candidate == a[i])//如果数据相同,计数加1
- {
- ntimes++;
- }
- else
- {
- ntimes--; //如果计数不同,则计数减1,相当于删除了两个元素
- }
- }
- }
- int count = 0;
- for(i = 0; i <length; i++)
- {
- if(candidate == a[i])
- count++;
- }
- //最终得到的candidate元素有可能是序列最末位的两个元素之一
- //因此,需要验证
- if(count > length/2)
- {
- cout << endl << "主元素为: " << candidate << endl;
- }
- else
- {
- cout << "没有主元素." << endl;
- }
- }
时间复杂度分析:遍历一次数组需要O(n)的时间,所以总的时间复杂度为O(n),且只需要常数的额外内存。
参考:《算法设计实验题解》、http://blog.sina.com.cn/s/blog_4ae8f77f0100uptr.html,感谢这位朋友的思路。
原文:http://www.cnblogs.com/bendantuohai/p/4483854.html
内容总结
以上是互联网集市为您收集整理的主元素 算法全部内容,希望文章能够帮你解决主元素 算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。