dtcms 模板下载 第三代半导体 Nginx环境搭建 html 劝酒文化 ISP matplotlib elasticsearch websocket interface variant ant requirejs vue下载 bootstrap后台管理模板 安卓项目实战 access教学视频 在线考试系统代码 hbase端口 matlab中axis java常用的包 pcie高速固态硬盘 安卓虚拟机运行windows oracle可视化工具 matlab自然对数 plsql连接mysql flutter ui构建工具 mysql时间戳转日期 python编程教程 python创建对象 python开发 python中re模块 java编程实例 java编程环境 java继承关键字 java在线课程 java的map java如何配置环境变量 java获取当前时间 javaabstract
当前位置: 首页 > 学习教程  > 编程语言

线性时间选择求第k小数(分治)

2020/11/4 14:23:09 文章标签:

线性时间选择 问题描述&#xff1a;给定线性序集中 n 个元素和一个整数 k&#xff08;1 < k < n&#xff09;&#xff0c;要求找出着 n 个元素中第 k 小的元素。 RandomizedSelect算法&#xff1a; 该算法实际上是模仿快速排序算法设计的&#xff0c;基本思想是对输入的…

线性时间选择

问题描述:给定线性序集中 n 个元素和一个整数 k(1 <= k <= n),要求找出着 n 个元素中第 k 小的元素。
RandomizedSelect算法:
该算法实际上是模仿快速排序算法设计的,基本思想是对输入的数组进行递归划分。与快速排序的算法不同的是,它只对划分的数组之一进行递归处理。

划分:以数组的第一个元素作为基准值,设置两个变量分别从前后往中间走,把大于基准值的放在基准值的右半部分,而小于基准值的放在基准值左侧。

int Partition(Type a[], int p, int r) {
	// 划分, 以 a[p] 为基准,一分为二 
	int i = p, j = r + 1;
	int x = a[p];
	while(1) {
		while(a[++i] < x && i < r) ;
		while(a[--j] > x && i >= p) ;
		if (j <= i) break;
		swap(a[i], a[j]);
	}
	a[p] = a[j];
	a[j] = x;
	return j;
}
template <class Type>
int RandomizedSelect(Type a[], int p, int r, int k) {
	// 线性时间选择找第 k 个小的数 
	if (p == r) return a[p];
	int ind = Partition(a, p, r);
	int j = ind - p + 1; // 左侧区间的长度 
	if (j >= k) {
		return RandomSelect(a, p, ind);
	} else {
		return RandomSelect(a, ind + 1, r, k - j);
	}
}

在算法RandomizedSelect执行Partition后,数组a[p:r]被划分成两个子数组:a[p:ind] 、 a[ind + 1, r], 使得每个a[p:ind]数组里的元素都不大于a[ind + 1 : r] 里的元素。接着算法执行计算子数组里面的元素个数,判断第 k 个小的元素落在哪一个区间里面,分治的思想,对其中一个区间进行递归调用算法。
容易看出,在最坏的情况下线性时间算法需要 O ( n 2 ) O(n^2) O(n2)计算时间。例如:再找最小元素时,总在最大元素处进行划分。尽管如此,该算法的平均性能比较好。

优化

对划分算法Partition进行优化,使用一个随机数产生器Random,随机的产生p-r之间的一个随机整数,即划分基准是随机的,这个时候线性时间算法的平均时间可以在 O ( n ) O(n) O(n)内找到。

template <class Type>
Type RandomizedPartition(Type a[], int p, int r) {
	int i = p, j = r + 1;
	//Type x = a[p];
	int s = (rand() % (r - p + 1) + p);  // 随机下标
	Type x = a[s];
	// 将小于 x 的元素放在左侧, 大于 x 的放在右侧 
	while(1) {
		while(a[++i] < x && i < r) ; // 找到一个不小于 x 的元素
		while(a[--j] > x && j >= p);
		if (i >= j) {
			break; // 全部完成,终止 
		} 
		swap(a[i], a[j]);
	}
	a[s] = a[j];
	a[j] = x;
	return j;
}

下面给出上述算法的验证截图:
在这里插入图片描述
全部代码在下面:

#include <cstdio>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <ctime>
#include "windows.h"
#define MAX_N 1000000
#define LEN 30
using namespace std;
/* 线性时间选择, 找第 k 小的元素 */ 

int arr[MAX_N + 5];
int n, mod, ind;

template <class Type>
Type RandomizedPartition(Type a[], int p, int r) {
	int i = p, j = r + 1;
	//Type x = a[p];
	int s = (rand() % (r - p + 1) + p); 
	Type x = a[s];
	// 将小于 x 的元素放在左侧, 大于 x 的放在右侧 
	while(1) {
		while(a[++i] < x && i < r) ; // 找到一个不小于 x 的元素
		while(a[--j] > x && j >= p);
		if (i >= j) {
			break; // 全部完成,终止 
		} 
		swap(a[i], a[j]);
	}
	a[s] = a[j];
	a[j] = x;
	return j;
}

template <class Type>
Type RandomizedSelect(Type a[], int p, int r, int k) {
	if (p == r) {
		ind = p;
		return a[p];
	}
	int i = RandomizedPartition(a, p, r); // 将数组 a 一分为 2 
	int j = i - p + 1;
	if (k <= j) 
		return RandomizedSelect(a, p, i, k);
	else 
		return RandomizedSelect(a, i + 1, r, k - j);
}
void set_console_color(unsigned short color_index)
{
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color_index);
}
int main() {
	srand(time(NULL)); /*根据当前时间设置“随机数种子”*/
	set_console_color(9);
	cout << "请输入数据规模 n 和最大数据 mod " << endl;
	set_console_color(7);
	cin >> n >> mod;
	set_console_color(9);
	cout << "请输入 k " << endl;
	set_console_color(7);
	int k;
	cin >> k;
	for (int i = 0; i < n; i++) {
		arr[i] = rand() % mod;
	}
	int ans = RandomizedSelect(arr, 0, n - 1, k);
	set_console_color(2);
	//cout << "ans = " << ans << endl;
    cout << "数组中第 " << k << " 小的数是 " << arr[ind] << endl;
   	set_console_color(7); 
	cout << "*******排序后的结果如下**********" << endl;
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) {
		if (i - ind)
			cout << arr[i] << " ";
		else {
			set_console_color(2);
    		cout << arr[i] << " ";
   			set_console_color(7); 	
   		}
		if (i && i % 30 == 0) cout << endl;
	}
	cout << endl;
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_350134.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?