/*****************************************************************
题目:输入n个整数,找出其中最小的k个数。例如输入4,5,1,6,2,7,3,8这
8个数字,则最小的4个数字是1,2,3,4。
*****************************************************************/
#include<iostream>
#include<set>
#include<vector>
using namespace std;
void swap(int* pNum1, int* pNum2)
{
int nTemp = *pNum1;
*pNum1 = *pNum2;
*pNum2 = nTemp;
}
int partition(int* numbers, int start, int end)
{
if(numbers == NULL || start>end)
throw new std::exception("invalid input!\n");
int standard = numbers[end];
int small = start-1;
for(int i=start; i<end; ++i)
{
if(numbers[i] < numbers[end])
{
++small;
if(i != small)
swap(&numbers[i],&numbers[small]);
}
}
++small;
swap(&numbers[small], &numbers[end]);
return small;
}
//方法1
//按照第29题的思路,可以给予partition来解决这个问题
//如果基于数组的第k个数字来调整,使得第比第k个数字小的所有
//数字都位于数组的左边,比第k个数字大的所有数字都位于数组的
//右边。这样调整后,位于数组中左边的k个数字就是最小的k个数
//时间复杂度为O(N)
void GetLeastNumbers(int* input,int n, int* output, int k)
{
if(input == NULL || n<=0 || output == NULL || k<=0 || k>n)
throw std::exception("invalid question!");
int start = 0;
int end = n-1;
int index = partition(input,start,end);
while(index!=k-1)
{
if(index>k-1)
{
end = index-1;
index = partition(input,start,end);
}
else
{
start = index + 1;
index = partition(input, start, end);
}
}
for(int i=0; i<k; ++i)
{
output[i] = input[i];
}
}
//方法2:特别适合处理海量数据
//用堆或者红黑树实现。先填满容器k个元素,后面的数字如果大于容器中最大值,、
//就将容器中最大值删除,加入新元素。
//这里采用multiset解决问题,它是由红黑树实现的
typedef multiset<int,greater<int>> intSet;
typedef multiset<int,greater<int>>::iterator setIterator;
void GetLeastNumbers(const vector<int>& data, intSet& leastNumbers,
int k)
{
leastNumbers.clear();
if(k<1 || data.size()<k) //输入无效
return;
vector<int>::const_iterator iter = data.begin();
for(;iter != data.end(); ++iter)
{
if((leastNumbers.size())<k)
leastNumbers.insert(*iter);
else
{
setIterator iterGreatest = leastNumber.begin();
if(*iter < *(leastNumbers.begin()))
{
leastNumbers.erase(iterGreatest);
leastNumbers.inset(*iter);
}
}
}
}
void test()
{
const int length = 8;
int input[length] = {4,5,1,6,2,7,3,8};
const int k = 4;
int output[k];
GetLeastNumbers(NULL,0,output,k);
for(int i=0; i<k; ++i)
{
printf("%d\t",output[i]);
}
}
int main()
{
try{
test();
}
catch(std::exception ex)
{
std::cerr<<ex.what();
}
return 0;
}
第一种方法复杂度第,但要改变输入的数据;而第二种方法不会改变输入的数据适用于n很大,k较小的问题
==参考剑指offer
分享到:
相关推荐
在N个数字中,删除K个,使剩余的数字最小。
给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个 新的正整数。对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正...
输入一个N位高精度的正整数,去掉其中任意K个数字后剩下的数字按原左右次序组成一个新的正整数。写算法对给定的N和K,寻找一种方案使得剩下的数字组成的新数最小。 输入:N、K以及一个N位高精度的正整数 输出:剩下...
这是一个用C++写的简单算法,里面没用到什么高深的东西,就是基本的控制语句组成。
本文实例讲述了Python实现查找最小的k个数。分享给大家供大家参考,具体如下: 题目描述 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 解法1 使用partition...
373._Find_K_Pairs_with_Smallest_Sums查找和最小的k对数字【LeetCode单题讲解系列】
例如数据集为:{1、8、3、6、5、4、7、2},则最小的4个数字为1,2,3和4。 【基本要求】 由随机数产生测试数据,测试数据不小于10000个,测试k的不同取值对算法的影响,如k=10、50、100、500、1000、2000等;在课程...
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 这个题目完成的思路有很多,很多排序算法都可以完成既定操作,关键是复杂度性的考虑。以下几种思路当是笔者...
问题描述: 给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列成一个新的正整数。 算法设计: 给定n (1)位的正整数a和k,...试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。
373.查找和最小的-k-对数字.cpp
例如,输入 4、5、1、6、2、7、3、8 这 8 个数字,则最小的 4 个数字是 1、2、3、4。示例 1:输出:[1,2] 或者 [2,1]示例 2:输出:
试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。 输入格式 可输入多组测试数据(不超过50组测试数据),每组测试数据分两行,每行一个数,数的含义如下。 第一行:正整数a(a是大于0的一个n...
从 n 个数字的列表中找到第 k 个最小的。 基于 Hoare 的 Quickselect 算法和三支点策略的中位数。 有关详细信息,请参阅https://en.wikipedia.org/wiki/Quickselect 。 可以通过传递 n+1-k 找到第 k 个*大*元素
示例 1:输出: [1,2],[1,4],[1,6]解释: 返回序列中的前 3 对数:示例 2:输出: [1,1],[1,1]解释: 返回序列中的前 2 对数:
问题描述: 给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列成一个新的正整数。 算法设计: 给定n (1)位的正整数a和k,...试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。
利用K-means聚类法将灰度图像划分成聚类分区, 在每个聚类分区应用最小平方法least-squares最小化二值半色调图像和原始灰度级图像之间的平方误差, 所构造的半色调算法与基于模型的最小平方法LSMB算法相比, 随着聚类...
否则数字表示节点间权值。 Output 输出最小生成树包括的节点 Sample Input 11 65535 9 59 69 96 11 72 100 17 43 28 9 65535 40 21 23 61 78 97 41 76 86 59 40 65535 39 48 55 64 11 85 23 44 69 21 39 ...
例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。值得一提的是,arraycopy使用的是native方法,用c++写的,因
问题描述: 给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列成一个新的正整数。 算法设计: 给定n (1)位的正整数a和k,...试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。
自己用C语言写的最小二乘法拟合 没有经过美化但能算100对以内的数字