`

分治法求第k小元素

    博客分类：
  • C
算法 
阅读更多

算法：http://www.cnblogs.com/chaofan/archive/2009/12/14/1623320.html

求一列数中的第k小元素，利用分治的策略进行递归求解。

首先随便指定一个数，这里我指定的是第一个数为第k小元素记为randK，将数组中其他的数与findK进行比较，比他小的放在左边，大的放在右边，如果randK左边的元素个数为k-1个，说明findK就是你所要找的元素，如果左边的元素个数>k-1，说明你要找的元素在左边的数中，继续使用相同的方法在左边的数中进行查找，如果左边的元素的个数<k-1,说明你要找的元素在右边的数中，则继续使用相同的办法在右边的数中进行查找。。。

代码：

#include <iostream>
using namespace std;

const int M = 999;
typedef struct Data 
{
	int data;
	bool flag;
}Mit[M];

int findP(int a [], int oP, int R)
{
	int randK = a[oP];
	int iL = oP + 1;
	int iR = R;
	while (true)
	{
		while (a[iL] < randK)
		{
			iL++;
		}
		while (a[iR] >= randK)
		{
			iR--;
		}
		if (iL >= iR)
		{
			break;
		}
		swap(a[iL], a[iR]);
	}
	swap(a[oP], a[iR]);
	return iR;
}

int findK(int a [], int oP, int n, int k)
{
	int find_k;
	int copy_k;
	find_k = findP(a, oP, n);
	copy_k = find_k - oP;
	if (k == copy_k)
	{
		return a[find_k];
	}
	if (k > copy_k)
	{
		return findK(a, find_k + 1, n, k - copy_k - 1);
	}
	if (k > copy_k)
	{
		return findK(a, oP, find_k - 1, k);
	}
	else
	{
		return 0;
	}
}

int main()
{
	int n;
	int k1, k2;
	Mit d;
	cout << "请输入无序列表的大小:" << endl;
	cin >> n;

	cout << "请输入无序列表中的所有元素" << endl;
	//输入无序列表中的所有元素
	for (int i = 0; i < n; i++)
	{
		d[i].flag = 1;
		cin >> d[i].data;
	}

	cout << "请输入k1, k2:" << endl;
	cin >> k1 >> k2;
	if (k1 < k2)
	{
		int temp = k1;
		k1 = k2;
		k2 = temp;
	}

	for (int i = 0; i < n; i++)
	{
		if (d[i].flag)
		{
			cout << d[i].data << endl;
		}
	}

	system("pause");
}

 

/************************************************************************/
/* 分治法求第k小元素                                                                     */
/************************************************************************/
//在随机生成的数组中求第K小的元素，并求比较次数   
#include<iostream>    
#include<iomanip>   
#include<ctime>   
#define SIZE 100    
#define swap(a,b) {int t=b;b=a;a=t;}      
using namespace std;
static int cn = 2;//定义静态全局变量，统计比较次数   

int partition(int a [], int l, int r)//返回中枢元素位置   
{
	int i = l - 1, j = r;
	int v = a[r];//把中枢元素赋给V   
	while (1)
	{
		while (a[++i] < v) 
			cn++;
		while (v < a[--j]) 
			cn++;
		if (i >= j)   
			break;
		swap(a[i], a[j]);//交换元素    
	}
	swap(a[i], a[r]);//交换中枢元素      
	return   i;//返回排序后的中枢元素位置   
}

int random_partition(int a [], int l, int r)//得到随机的中枢函数   
{
	srand(time(0));//初始化种子     
	int i = rand() % (r - l + 1) + l;//中枢元素随机划分       
	swap(a[i], a[r]);//把中枢元素放在开头位置   
	return   partition(a, l, r);//返回中枢元素位置    
}

int random_select(int a [], int l, int r, int k)
{
	if (r <= l)   return   a[r];
	int   i = random_partition(a, l, r);//返回中枢元素位置    
	int   j = i - l + 1;//求得元素个数   
	if (j == k)//判断是否为第K小，是则返回该元素     
		return  a[i];
	if (j > k)//小于第K小的元素个数多于K，则在左子集中寻找第K小的元素，否则在右子集中寻找   
		return   random_select(a, l, i - 1, k);
	else
		return   random_select(a, i + 1, r, k - j);

}

void disp(int a [], int n)//输出随机生成的数组元素   
{
	int k = -1;
	for (int i = 0; i < n; i++){

		k++;
		if (k % 5 == 0)
			cout << endl;
		cout << setw(2) << i << ":" << setiosflags(ios::left) << setw(12) << a[i];
	}
	cout << endl;


}

int main()
{

	int i, a[SIZE];//定义数组   
	srand((unsigned int) time(0));//初始化种子   
	for (i = 0; i <= 100; i++)
		a[i++] = rand();//随机化数组   
	cout << "生成的随机数为:" << endl;
	disp(a, SIZE);//输出生成的数组元素      
	int k;
	cout << "------求第K小的数------" << endl;
	cout << "请输入K:" << endl;
	cin >> k;
	cout << "第" << k << "小的数是:" << (random_select(a, 0, SIZE - 1, k)) << endl;
	cout << "比较次数为:" << cn << endl;
	return 0;
}

 

#include<iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
#define  Array_max 200

void swap(int &a, int &b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
}

void out(int a [], int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
		if (i%8 == 0 && i != 0)
		{
			cout << endl;
		}
	}
	cout << endl;
}

int findP(int a [], int oP, int R)
{
	int randK = a[oP];
	int iL = oP + 1;
	int iR = R;
	while (true)
	{
		while (a[iL] < randK)
		{
			iL++;
		}
		while (a[iR] >= randK)
		{
			iR--;
		}
		if (iL >= iR)
		{
			break;
		}
		swap(a[iL], a[iR]);
	}
	swap(a[oP], a[iR]);
	return iR;
}

int findK(int a [], int oP, int n, int k)
{
	int find_k;
	int copy_k;
	find_k = findP(a, oP, n);
	copy_k = find_k - oP;
	if (k == copy_k)
	{
		return a[find_k];
	}
	if (k > copy_k)
	{
		return findK(a, find_k + 1, n, k - copy_k - 1);
	}
	if (k > copy_k)
	{
		return findK(a, oP, find_k - 1, k);
	}
	else
	{
		return 0;
	}
}

void main()
{
	int n;
	int k;
Begin:
	cout << "Please input the length of your Array:";
	cin >> n;
	cout << endl;
	int *a = new int[n];
	srand((unsigned) time(NULL));
	for (int i = 0; i < n; i++)
	{
		a[i] = rand()%100;
	}
	cout << "The Random_Array_element is:" << endl;
	out(a, n);
	cout << "Please input the K:";
	cin >> k;
	if (k > n)
	{
		goto Begin;
	}
	else
	{
		cout << "The element you find now is:" << findK(a, 0, n - 1, k - 1) << endl;
	}

	system("pause");
}

 

#include<iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
#define  Array_max 200

void swap(int &a, int &b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
}

void out(int a [], int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
		if (i % 8 == 0 && i != 0)
		{
			cout << endl;
		}
	}
	cout << endl;
}

int findP(int a [], int oP, int R)
{
	int randK = a[oP];
	int iL = oP + 1;
	int iR = R;
	while (true)
	{
		while (a[iL] < randK)
		{
			iL++;
		}
		while (a[iR] >= randK)
		{
			iR--;
		}
		if (iL >= iR)
		{
			break;
		}
		swap(a[iL], a[iR]);
	}
	swap(a[oP], a[iR]);
	return iR;
}

int findK(int a[], int oP, int n, int k)
{
	int find_k;
	int copy_k;
	find_k = findP(a, oP, n);
	copy_k = find_k - oP;
	if (k == copy_k)
	{
		return a[find_k];
	}
	if (k > copy_k)
	{
		return findK(a, find_k + 1, n, k - copy_k - 1);
	}
	if (k > copy_k)
	{
		return findK(a, oP, find_k - 1, k);
	}
	else
	{
		return 0;
	}
}

void main()
{
	int n;
	int k1, k2;
Begin:
	cout << "Please input the length of your Array:";
	cin >> n;
	cout << endl;
	int *a = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	cout << "The Random_Array_element is:" << endl;
	out(a, n);
	cout << "Please input the K1,k2(k1 < k2):";
	cin >> k1>>k2;
	if (k1 > n || k2 > n)
	{
		goto Begin;
	}
	else
	{
		int x = findK(a, 0, n - 1, k1);
		int y = findK(a, 0, n - 1, k2);
		int i;
		/*cout << "The element you find now is:" << findK(a, 0, n - 1, k) << endl;*/
		for (i = 0; i < n; i++)
		{
			if (a[i] != x ||a[i] != y)
			{
				a[i] = 0;
			}
			else
			{
				break;
			}
			
		}
		for (i = n - 1; i > 0; i++)
		{
			if (a[i] != x || a[i] != y)
			{
				a[i] = 0;
			}
			else
			{
				break;
			}
		}
	}

	for (int i = 0; i < n;i++)
	{
		if (a[i] != 0)
			cout << a[i] << " ";
	}
	
	system("pause");
}

 

    //在随机生成的数组中求第K小的元素，并求比较次数   
    #include<iostream>    
    #include<iomanip>   
    #include<ctime>   
    #define SIZE 100    
    #define swap(a,b) {int t=b;b=a;a=t;}      
    using namespace std;    
    static int cn=2;//定义静态全局变量，统计比较次数   
       
    int partition(int a[],int l,int r)//返回中枢元素位置   
        {                    
                  int i=l-1,j=r;      
                  int v=a[r];//把中枢元素赋给V   
                  while(1)      
                  {      
                      while(a[++i]<v) cn++;      
                      while(v<a[--j]) cn++;   
                          if(i>=j)   break;      
                          swap(a[i],a[j]);//交换元素    
                  }      
                  swap(a[i],a[r]);//交换中枢元素      
                  return   i;//返回排序后的中枢元素位置   
        }      
             
    int random_partition(int a[], int l, int r)//得到随机的中枢函数   
      {      
                srand(time(0));//初始化种子     
                int i=rand()%(r-l+1)+l;//中枢元素随机划分       
                swap(a[i],a[r]);//把中枢元素放在开头位置   
                return   partition(a,l,r);//返回中枢元素位置    
      }      
             
    int random_select(int a[],int l,int r,int k)      
        {      
                if(r<=l)   return   a[r];      
                int   i=random_partition(a,l,r);//返回中枢元素位置    
                int   j=i-l+1;//求得元素个数   
                if(j==k)//判断是否为第K小，是则返回该元素     
                      return  a[i];      
                if(j>k)//小于第K小的元素个数多于K，则在左子集中寻找第K小的元素，否则在右子集中寻找   
                      return   random_select(a,l,i-1,k);      
                else      
                      return   random_select(a,i+1,r,k-j);                
             
        }        
           
    void   disp(int a[],int n)//输出随机生成的数组元素   
    {              
                    int k=-1;   
                  for(int i=0;i<n;i++){   
                         
                      k++;   
                      if(k%5==0)   
                          cout<<endl;   
                      cout<<setw(2)<<i<<":"<<setiosflags(ios::left)<<setw(12)<<a[i];}   
                  cout<<endl;   
       
                              
        }      
           
    int main()      
        {            
                 
              int i,a[SIZE];//定义数组   
              srand((unsigned int)time(0));//初始化种子   
              for(i=0;i<=100;i++)   
                  a[i++]=rand();//随机化数组   
              cout<<"生成的随机数为:"<<endl;   
              disp(a,SIZE);//输出生成的数组元素      
              int k;   
              cout<<"------求第K小的数------"<<endl;   
              cout<<"请输入K:"<<endl;   
              cin>>k;      
              cout<<"第"<<k<<"小的数是:"<<(random_select(a,0,SIZE-1,k))<<endl;   
              cout<<"比较次数为:"<<cn<<endl;   
              return 0;   
    }

 

分享到：
| Is Programming Boring?
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    分治法求第K大的数字

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

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

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

    用分治法实现元素选择

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

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

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

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

    ### C++实现分治法求最大值 在给定的代码示例中，我们看到了分治法用于寻找数组最大值的具体实现。代码的核心是`Max`函数，它接受一个整数数组`a[]`及其下标范围`low`和`high`作为参数。该函数首先检查边界条件： ...

    算法：求第k小元素

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

    第K小元素（分治法）

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

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

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

    分治法求众数

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

    实验4 分治法1

    1. **元素选择**：给定一个序列和一个整数k，找到序列中第k小的元素及其位置。不需对序列进行排序，需要设计一个有效的算法来找到第k小的元素。 2. **最大子段和问题**：对于一个整数序列，找到和最大的连续子序列...

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

    在计算机科学和编程领域，寻找第k小元素是一项常见的任务，它涉及到排序和搜索算法的知识。这个主题是对基本算法的复习，旨在强化我们对高效解决问题的理解。在此，我们将深入探讨几种寻找第k小元素的算法，并分析...

    fenzhi.zip_K.

    传统的分治法求第k小元素的思路通常是通过划分数组，然后根据中间值的位置来决定k在哪一侧。然而，对于寻找k1到k2范围内的元素，这种方法并不直接适用，因为每次划分只能保证找到一个特定位置的元素，而不是一段范围...

    分治法-中位数

    分治法是一种重要的算法设计思想，其核心在于将一个复杂的问题分解成若干个规模较小但结构相似的子问题，然后递归地解决这些子问题，并将各个子问题的解组合起来得到原问题的解。分治法在很多情况下都能达到较高的...

    算法设计部分习题答案

    4. **分治法求第k小元素**：分治法是一种将大问题分解为小问题并逐个解决的策略。求解第k小元素的问题可以使用快速选择算法，它是快速排序的一个变种，专门用于查找序列中的第k小（或第k大）元素，平均时间复杂度为O...

    分治法实现矩阵相乘

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

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

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

    求第K大元素

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

    分治法的应用

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

    算法作业 第K小问题

    这是算法作业，C++，分治原理解决第k小问题，只有cpp

    寻找第k小元素(vc)

    5. **二分查找法**：对于已排序的数组，可以结合二分查找来找到第k小的元素。首先找到数组中第一个大于等于k的元素，然后在此元素之前的子数组中再寻找第k-1小的元素。这种方法适用于有序数组，时间复杂度为O(log n)...

Magicbox
Global site tag (gtag.js) - Google Analytics