首页 > 基础算法 > 排序 > 求第二小元素-算法导论习题
2014
05-06

求第二小元素-算法导论习题

一、题目

证明:在最坏情况下,利用n+ceil(lg n)-2次比较,即可得到n个元素中的第2小元素。(提示:同时找最小元素)。ceil表示向上取整

二、思考

step1:对所有元素,两个一组比较大小,小的一个进入下一轮比较。一直到比较出最小的元素。此时所有比较结果构成一棵二叉树。比较次数为n-1。
step2:沿着树从树根向下到叶子,找出第二小的元素,比较次数是ceil[lgn]-1。令m2[p]表示以p为根的树中的第二小元素。对于当前处理结点为p,key[p] = min{key[left[p]], key[right[p]]}。假设key[p] =  key[left[p]],则m2[p] = min{m2[left[p]], key[right[p]]}
可以这么理解:先找到最小的元素X,需要 n-1次比较。只有和X比较过的元素才有可能为 第二小,和X比较过的元素个数为 ceil(lg n) 个,需要比较ceil(lg n)-1次,即上面蓝色圈中的数字。即总得比较次数为:n+ceil(lg n)-2

三、代码

#include <iostream>
using namespace std;
//第一遍求最小值的结果用树表示
struct node
{
	int key;
	node *next;//指向同一层中的下一个元素
	node *p;
	node *left;
	node *right;
	node(int k):key(k),next(NULL),p(NULL),left(NULL),right(NULL){}
};
//求第二小值
int Find_S2(node *head)
{
	node *p, *q, *r, *t;
	//step1:求最小值
	//两两比较,较小的一个进入下一轮,这个循环当只剩下一个元素时结束
	while(head->next != NULL)
	{
		//从第一个元素开始,head指向比完后较小的那一组数据中的第一个
		p = head;head = NULL;
		while(p)
		{
			//如果这组数据有奇数个,最后一个元素直接晋级
			if(p->next == NULL)
			{
				r = new node(p->key);
				r->left = p;
				p->p = r;
				p = p->next;
			}
			//p与p->next比较,较小的元素晋级
			else
			{
				q = p->next;
				r = new node(min(p->key, q->key));
				r->left = p;
				r->right = q;
				p->p = r;
				q->p = r;
				p = q->next;
			}
			//head指向比完后较小的那一组数据中的第一个,t用于把head指向的数据链成链表
			if(head == NULL)
			{
				head = r;
				t=  head;
			}
			else
			{
				t->next = r;
				t = r;
			}
		}
	}
	//step2:求最第二小值
	//Min用于存储最小值,Min2用于存储第二小值
	int Min = head->key, Min2 = 0x7fffffff;
	//从根结点向下比较
	p = head;
	//比较到叶子结点时循环结束
	while(p->left != NULL)
	{
		//当前结点的值来源于右孩子
		if(p->right && p->right->key == Min)
		{
			Min2 = min(Min2, p->left->key);
			p = p->right;
		}
		//当前结点的值来源于左孩子
		else
		{
			//由左孩子直接晋级的情况
			if(p->right)
				Min2 = min(Min2, p->right->key);
			p = p->left;
		}
	}
	return Min2;
}
//测试
int main()
{
	int A[8] = {0};
	node *head = NULL;
	//生成8个随机测试数据
	for(int i = 0; i < 8;i++)
	{
		A[i] = rand() % 100;
		//构造成树的最底层结点
		node *p = new node(A[i]);
		p->next = head;
		head = p;
	}
	//运行算法并输出结果
	cout<<Find_S2(head)<<endl;
	return 0;
}
转自:http://blog.csdn.net/mishifangxiangdefeng/article/details/7983809

  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])