#include <iostream>
#include <vector>
using namespace std;
#define EXCHANGE(a,b) \
({typeof(a) _tmp; \
_tmp=a; \
a=b; \
b=_tmp;})
template <typename T>
int Partition(vector<T>& arr,int p,int r){
int x=arr[r];
int i=p-1;
int j=0;
for(j=p;j<=r-1;j++){
if(arr[j]<=x){
i=i+1;
EXCHANGE(arr[i],arr[j]);
}
}
EXCHANGE(arr[i+1],arr[r]);
return i+1;
}
template <typename T>
void FIND_K(vector<T>& arr,int first,int last,int K){
int index;
index = Partition(arr,first,last-1);
if(index == K)
return;
else if(K < index)
FIND_K(arr,first,index,K);
else
FIND_K(arr,index+1,last,K);
return;
}
int main()
{
int arr[] = {250,300,350,400,400,\
450,500,500,550,650,\
655,700,725,735,750};
int K;
int N = sizeof(arr)/sizeof(int);
vector<int> Arry(arr,arr+N);
K = N/2;
FIND_K(Arry,0,N,K);
cout<<Arry[K]<<endl;
return 0;
}
从一组未排序的数组里找到第K大元素 用快速排序的思想 可以减少一半的排序量
分享到:
相关推荐
学习算法时一个求第k小元素的小例子。内含代码和输入文件。很好用哦!
已知两个等长的升序整数序列{a1, a2, ..., ak}和{b1, b2, ..., bk},求序列{ai+bj}的前k小元素,其中1≤i≤k且1≤j≤k,要求时间复杂度尽可能低。 思路:将(1,1,a1+b1)加入一个小根堆 while (堆非空且出堆的...
可以运行的查找第K小元素的实现代码。并且实现了多个元素相同的算法。与王晓东的《算法》配套
寻找数组中第k大的元素,基于快速排序思想,实践复杂度为O(n)
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明:你可以假设 k 总是有效...
题目就是要求O(n)复杂度求无序列表中第K的大元素 如果没有复杂度的限制很简单。。。加了O(n)复杂度确实有点蒙 虽然当时面试官说思路对了,但是还是没搞出来,最后面试官提示用快排的思想 主要还是设立一个flag,列表...
分析:求解k个数的不同...素是不重复的,可以约定其递增排列,因为数组中的元素是递增排列的: 所以a[k-1]即组合中的最后一个数,只能为k~n 令i=a[k-1] 则 i>=k && i 完整代码请参考我的博客文章,这里只是核心部分
1. 设计程序利用分治策略求n个数的最大值和最小值。 2. 利用分治策略,在n个不同元素中找出第k个最小元素。
*功能:从两个排好序的数组A[1..m]、B[1..n]中 *找出第K大的元素。 *时间复杂度为O(lg(m)+lg(n))
给定线性序集中n个元素和一个整数k,1<=k,要求找出这n个元素中第k小的元素,即如果将这n个元素依其线性续排列时,排在第k个位置的元素即为要找的元素。当k=1时,就是要找的的最小元素,当k=n时,就要找到最大的元素...
由于只需要找出前k大的数,因此没必要对数组中所有的元素排序,可以采用部分排序的方式。具体思路为:第一次先遍历数组找到最大的数,第二次遍历从剩下的数组中找到最大的数(在整个数组中第二大的数)…共需遍历k次...
使用由 C-MEX 实现的部分快速排序算法。 复杂度为 O(n + k.log(k)),其中 n 是数组的大小,k 是要选择的元素数。 对于大尺寸输入,比 SORT 或多次调用 MIN/MAX 快。 支持多维能力
如何在某集合里面找出最大或最小的K个元素。 解决思路: 找出最大或最下的K个元素,可以使用Python库中的heapq模块,该模块提供两个函数nlargest()求最大K个和nsmallest()求最小K个。 下面我们举例说明: import ...
今天做到的一道题,在数组中找到第n大的元素。 样例1: 输入:n = 1, nums = [1,3,4,2] 输出:4 样例2: 输入:n = 3, nums = [9,3,2,4,8] 输出:4 在数组中找到第n大的数,我首先想到的是用python的列表方法sort()...
解法2: 利用选择排序或交互排序,K次选择后即可得到第k大的数。总的时间复杂度为O(n*k) 解法3: 利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。...
设R={r1,r2,…,rn}是要进行排列的n个元素,R的全排列记为perm(R),Ri=R-{ri},(ri)perm...3. 从排列 1 2 3 … n 开始,找其中的最大活动元素k,将该元素k与它所指向的相邻元素交换位置,并改变所有大于k的元素的方向。
本文实例讲述了C++实现的O(n)复杂度内查找第K大数算法。分享给大家供大家参考,具体如下: 题目:是在一组数组(数组元素为整数,可正可负可为0)中查找乘积最大的三个数,最后输出最大乘积。 从题目我们知道只有两...
现有长度为n的一个整数序列,要求你从中找出一个最长的子段,使得子段的最大元素与最小元素差的在[m,k]之间。 实验任务: 现在给你n、m、k以及n个整数,请输出满足条件最大子段的长度。 数据输入: 输入数据第一行包...
在两有序数组找第K个最小数 FindNotDouble 找只出现一次的元素 FindOnlyDup 找只重复一次的元素 FindOnlyDupBetweenTwo 两数组找出唯一不同的元素 FindMaxRecursion 递归求最大值 FindMaxDiff 找最大差值(动态规划) ...
二分查找算法是运用分治的典型例子:给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。所以容易设计出二分搜索算法:在 a[0] [1] [n-1] 中搜索 x, 找到x时返回其在数组中的位置,否则返回-...