`

分治法求第K大元素2

阅读更多
#include<iostream>
#include<algorithm>
using namespace std;

/***************************************
* 选择第k小元素算法
*
* 输入:元素数组A[],元素个数n,求的k
* 输出:第k小元素
***************************************/
template<class Type>
Type select(Type A[], int n, int k){
	int i, j, s, t;
	Type m, *p, *q, *r;
	if (n<38){                     //     如果元素个数小于38:则直接排序
		sort(A, A + n);
		return A[k - 1];
	}
	p = new Type[3 * n / 4];
	q = new Type[3 * n / 4];
	r = new Type[3 * n / 4];
	for (i = 0; i<n / 5; i++){  //        五个一组,把每组的中值元素存放进数组p
		mid(A, i, p);
	}
	m = select(p, i, i / 2 + i % 2);      //    递归调用,取得中值元素存入m
	i = j = s = 0;
	for (t = 0; t<n; i++) //  按<m、=m、>m把数组分成三组
	{   
		if (A[t]<m){
			p[i++] = A[t];
		}
		else{
			if (A[t] == m){
				q[j++] = A[t];
			}
			else{
				r[s++] = A[t];
			}

		}
	}
	if (i>k){                                //      若k<i,则该元素就在数组p中,进入p继续查找
		return select(p, i, k);
	}
	else{
		if (i + j >= k){               //   若i<k<i+j,则该元素在q数组中,即值为m
			return m;
		}
		else{        //        若k>i+j,则该元素在r数组中,进入r继续寻找
			return select(r, s, k - i - j);
		}
	}
}

/***************************************
* 计算中值元素
*
* 输入:元素数组A[],组号i
* 输出:存放中值元素的数组p[]
***************************************/
template<class Type>
void mid(Type A[], int i, Type p[]){
	int k = 5 * i;
	if (A[k]>A[k + 2]){
		swap(A[k], A[k + 2]);
	}
	if (A[k + 1]>A[k + 3]){
		swap(A[k + 1], A[k + 3]);
	}
	if (A[k]>A[k + 1]){
		swap(A[k], A[k + 1]);
	}
	if (A[k + 2]>A[k + 3]){
		swap(A[k + 2], A[k + 3]);
	}
	if (A[k + 1]>A[k + 2]){
		swap(A[k + 1], A[k + 2]);
	}
	if (A[k + 4]>A[k + 2]){
		p[i] = A[k + 2];
	}
	else{
		if (A[k + 4]>A[k + 1]){
			p[i] = A[k + 4];
		}
		else{
			p[i] = A[k + 1];
		}
	}
}

int main()
{
	int n, m;
	int x, y;
	int k1, k2;
	cout << "请输入数组元素个数:";
	cin >> n;
	cout << "请输入要求的k1,k2:";
	cin >> k1;
	cin >> k2;

	int *A = new int[n];
	int i;

	cout << "请输入数组元素:" << endl;
	for (i = 0; i<n; i++){
		cin >> A[i];
	}
	x = select(A, n, n - k1 + 1);
	y = select(A, n, n - k2 + 1);
	//cout << "第" << m << "大元素是:";
	//cout << select(A, n, n - m + 1) << endl;    // 输出第(n-m+1)小元素<=>第m大元素
	//获取数组下标方式
	for (int i = 0; i < n;i++)
	{
		if (A[i] == x || A[i] == y)
		{
			k1 = i;
			break;
		}
	}
	for (int i = n; i > 0; i--)
	{
		if (A[i] == x || A[i] == y)
		{
			k2 = i;
			break;
		}
	}
	for (; k1 <= k2;k1++)
	{
		cout << A[k1] <<" ";
	}
	system("pause");
	return 0;
}

 

#include<iostream> 
using namespace std;
#define max  100 
typedef struct Data
{
	int data;
	bool flag;
}Data, Mat[max];
Mat a;
void Found_k1_k2(Mat &a, int n, int k1, int k2)//用减治法查找无序列表中第k1到第k2小的整数 
{
	int x = 0;
	int y = n - 1;
	while (x<k1 - 1 || y>k2 - 1)
	{
		int temp;
		int f1, f2;//存储最小和最大数的下标 
		f1 = x;
		f2 = y;
		for (int i = x; i <= y; i++)
		{
			if (a[f1].data > a[i].data)
				f1 = i;    if (a[f2].data < a[i].data)
				f2 = i;
		}
		if (x < k1 - 1)
		{
			temp = a[x].data;
			a[x].data = a[f1].data;
			a[f1].data = temp;
			a[x].flag = 0;
			x++;
		}
		if (y > k2 - 1)
		{
			temp = a[y].data;
			a[y].data = a[f2].data;
			a[f2].data = temp;
			a[y].flag = 0;
			y--;
		}
	}
}
void Show(Mat &a, int n, int k1, int k2)
{
	cout << "第" << k1 << "小到" << k2 << "小之间的所有整数有:";
	for (int i = 0; i < n; i++)
	{
		if (a[i].flag)
			cout << a[i].data << "  ";
	}
	cout << endl;
}
void main()
{
	int choice;
	cout << "                       1: 执行程序 2: 退出程序" << endl;
	do
	{
		cout << "请选择你的操作:";
		cin >> choice;
		switch (choice)
		{
		case 1:
		{      int n;
		int k1, k2;
		cout << "请输入无序列表n的大小:";
		cin >> n;
		cout << "请输入无序列表中的所有整数:";
		for (int i = 0; i < n; i++)
		{
			a[i].flag = 1;
			cin >> a[i].data;
		}
		cout << "请输入k1k2的值:";
		cin >> k1 >> k2;
		if (k1 > k2)
		{
			int temp = k1;
			k1 = k2;
			k2 = temp;
		}
		if (k1<0 || k2>n || n < 0)
		{
			cout << "输入不和法!!请重新输入!!" << endl;
			break;
		}
		Found_k1_k2(a, n, k1, k2);
		Show(a, n, k1, k2);
		break;
		}
		case 2:
		{
				  cout << "退出程序";
				  break;
		}
		default:cout << "选择不合理请重选" << endl;
		}
	}
	while (choice != 2);
}

 

#include<iostream> 
using namespace std;
#define  swap(x, y) {int a = x; x = y; y = a;}
#define max  100 
typedef struct Data
{
	int data;
	bool flag;
}Data, Min[max];
Min a;
void Binary_search(Min &a, int n, int k1, int k2)
{
	//用减治法查找无序列表中第k1到第k2小的整数 
	int x = 0;
	int y = n - 1;
	while (x < k1 - 1 || y > k2 - 1)
	{
		int temp;
		//存储最小和最大数的下标 
		int f1, f2;
		f1 = x;
		f2 = y;
		
		for (int i = x; i <= y; i++)
		{
			if (a[f1].data > a[i].data)
				f1 = i;    //缩小空间
			if (a[f2].data < a[i].data)
				f2 = i;
		}
		//下面两段if相当于把不在k1,k2范围内的数组元素统统删掉
		if (x < k1 - 1)
		{
			temp = a[x].data;
			a[x].data = a[f1].data;
			a[f1].data = temp;
			a[x].flag = 0;
			x++;
		}
		if (y > k2 - 1)
		{
			temp = a[y].data;
			a[y].data = a[f2].data;
			a[f2].data = temp;
			a[y].flag = 0;
			y--;
		}
	}

	cout << "第" << k1 << "小到" << k2 << "小之间的所有整数有:";
	for (int i = 0; i < n; i++)
	{
		if (a[i].flag)
			cout << a[i].data << "  ";
	}
	cout << endl;
}

void main()
{
	    int n;
		int k1, k2;
		cout << "请输入无序列表大小::";
		cin >> n;
		cout << "请输入无序列表中元素:";
		for (int i = 0; i < n; i++)
		{
			a[i].flag = 1;
			cin >> a[i].data;
		}
		cout << "请输入k1k2的值:";
		cin >> k1 >> k2;
		if (k1 > k2)
			swap(k1, k2);
		if (k1<0 || k2>n || n < 0)
		{
			cout << "输入不合法!" << endl;
		}
		Binary_search(a, n, k1, k2);
		system("pause");
}

 

分享到:
评论

相关推荐

    分治法求第K大的数字

    利用分治法,解决对N个字中求第K大的数字的问题,效率比起逐个扫描有素提高

    找第K小问题C语言-分治法

    总的来说,找第K小问题的C语言分治法实现虽然代码可能显得有些复杂,但其背后的算法思路清晰明了。通过递归地划分和解决子问题,我们可以高效地在大规模数据中找到第K小的元素。这种分治策略在处理大量数据时尤其...

    分治法求最大值的C++实现

    在计算机科学领域,分治法(Divide and Conquer)是一种高效的问题解决策略,它将一个复杂的大问题分解成若干个相同或相似的子问题,直到这些子问题变得足够简单,可以直接求解为止。这种方法在处理诸如排序、查找...

    用分治法实现元素选择

    在这个特定的问题中,我们要利用分治法来实现“元素选择”,即找出线性序列集中第k小的元素及其位置。下面我们将深入探讨这个过程。 首先,理解问题的关键在于如何有效地比较并排序序列中的元素。分治法的基本步骤...

    用分治法求最大与最小值的问题

    在计算机科学中,分治法是一种重要的算法设计策略,它将一个大问题分解为若干个相同或相似的小问题,然后分别解决这些小问题,最后再将小问题的解合并成原问题的解。这个方法在处理复杂计算问题时非常有效,尤其是在...

    分治法求众数

    分治法求众数的时间复杂度主要取决于数据集的大小N和每次划分的子集数量K。如果每次划分成两半,那么时间复杂度约为O(N log N)。空间复杂度取决于分治深度,一般也是O(log N)。 **实际应用** 分治法求众数在处理大...

    实验4 分治法1

    分治法是计算机科学中一种重要的算法设计策略,它将一个大问题分解为若干个小问题来解决。这种思想源于“分而治之”,旨在通过解决小规模问题来构建大规模问题的解决方案。在这个实验中,我们将深入理解分治法的核心...

    分治算法求最大值与最小值,找最小元素

    传统的做法是遍历整个数组,但采用分治法可以更快地完成这一任务。基本步骤如下: 1. 将数组分为两个相等(或近乎相等)的部分。 2. 分别在左右两部分中独立找出最大值和最小值。 3. 比较左右两部分的最大值,取较...

    算法:求第k小元素

    在计算机科学中,"求第k小元素"是算法设计中的一个重要问题,它涉及到排序和查找的技巧。这个问题的目标是从一个未排序或者部分排序的数组或集合中找到第k个最小的元素,其中k通常是一个正整数。这个问题在数据分析...

    求第K大元素

    在编程和算法设计中,"求第K大元素"是一个常见的问题,特别是在数据处理和排序算法的场景下。这个问题的基本目标是从一个数组或集合中找出第K个最大的元素,其中K通常是一个正整数,且K小于等于数组的元素个数。这个...

    第K小元素(分治法)

    给定一个线性序列集,要求求出其中指定的第K小的数的值和位置,如给定n个元素和一个整数i,1≤i≤n,输出这n个元素中第i小元素的值及其位置

    分治法解快速排序,对称搜索及最大字段和

    它的核心思想是分治法(Divide and Conquer),即将一个大问题分解为两个或更多的小问题来解决。分治法通常包括三个步骤:分解、解决和合并。在快速排序中,分解通常是选择一个基准元素,将数组分为两部分,一部分的...

    分治法-中位数

    ### 分治法求解两个有序数组的中位数 #### 分治法简介 分治法是一种重要的算法设计思想,其核心在于将一个复杂的问题分解成若干个规模较小但结构相似的子问题,然后递归地解决这些子问题,并将各个子问题的解组合...

    分治法实现矩阵相乘

    分治法是一种解决复杂问题的有效策略,它将大问题分解为小问题来解决,然后合并小问题的解得到大问题的解。本篇文章将详细讨论如何利用分治法实现矩阵相乘。 矩阵相乘的基本概念是,两个矩阵A(m×n)和B(n×p)...

    分治法的应用

    这时,分治法的设计思路就是将大问题分解为多个较小的子问题,然后逐个解决这些子问题,最后将这些子问题的解合并起来形成原问题的解。 #### 三、分治法的适用条件 分治法能够有效解决的问题通常具备以下特征: 1...

    寻找第k小元素 基本算法复习

    对于寻找第k小元素,我们可以构建一个大顶堆,然后将堆顶元素(最大值)替换为下一个元素并重新调整堆。重复此过程k-1次,最后堆顶的元素就是第k小元素。堆排序法的时间复杂度为O(n log k),其中n是数组长度。 3. ...

    矩阵乘法(分治法)

    在矩阵乘法的分治法中,我们需要定义一些整型变量和若干个二维数组来存储矩阵的元素。因此,算法的空间复杂度是 O(n^2)。 矩阵乘法的分治法可以广泛应用于机器学习、计算机视觉、数据挖掘等领域。例如,在机器学习...

    矩阵乘法(分治法)内附实验报告

    在C++中实现分治法的矩阵乘法,我们需要定义矩阵类,包含矩阵元素的存储、基本操作如加法和乘法。在乘法函数中,我们首先检查矩阵的大小,如果满足分治的条件,则继续分解;否则,执行基本的元素级乘法。递归过程...

    最近对问题 分治法 ——C语言代码

    分治法是计算机科学中一种重要的算法设计策略,它的核心思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。在C语言中实现分治法,...

    算法设计策略 - 05-2 分治法.pdf

    最后,分治法不仅在排序和搜索算法中有应用,在很多其他领域的问题求解中也发挥着重要作用,如选择问题中的选最大元、选最小元以及选第k小元等。通过将问题分解为更小的子问题,分治法能够简化复杂问题的求解过程,...

Global site tag (gtag.js) - Google Analytics