专业团队为您服务的句子,上海seo公司哪家好,学生html美食静态网页代码,建立网站第一步1 问题
输入N个整数#xff0c;找出其中最小的K个#xff0c;例如输入数组6、5、1、4、 2、 7、 3、 8#xff0c;最小的4个数是1、2、3、4 2 分析
1#xff09;我们可以用快速排序从小到大#xff0c;但是时间复杂度是O(nlogn) 我们取出最前面的K个数就行。
2#xf…1 问题
输入N个整数找出其中最小的K个例如输入数组6、5、1、4、 2、 7、 3、 8最小的4个数是1、2、3、4 2 分析
1我们可以用快速排序从小到大但是时间复杂度是O(nlogn) 我们取出最前面的K个数就行。
2用partition算法时间复杂度是O(n)
我之前的博客讲解partition算法的总结如下
我们使用partition算法的时候从我们上面代码第一次调用来看我们选择的第一个数字5作为中间轴然后执行一次后我们的 partition函数返回的start或者i值都是4然后我们最后一步把5也插入了vector[4]那里就是说明我们左边有4个值比当前数字5作为中间轴都小也能说明这左边的4个值和中间轴数5都是数组里面最小的5个值如果我们需要求出一个数组里面最小的5个值我们只需要partition算法返回值是4就行然后在左边的数组的前5个数字就是这个数组里面最小的5个数所以这里的数组里面最小的多少K个数确保partition返回的index或者start的关系是index K - 1; 或者start K -1关系也就是说partition函数返回index或者start值的时候数组里面从坐标0到index或者start的值就是数组里面最小的元素也就是index1个元素。
简言之也就是说我们只需要确保partition算法这里返回值是3就行然后我们再取数组前面的4个数字就是我们需要得到的结果
优点这里时间复杂度为O(n)。
缺点修改了数组的数据然后适合数组数据量比较小。 3 我们单独可以一个空间这里用mulitSet 配上greater 就可以使得数据可以按照从大到小排序而且中间数据的插入删除查找的时间复杂度可以保持在O(logk) )保存K个数然后遍历所有数据如果这个数据小于空间K个数的最大值我们把空间最大值踢出来把这个数添加到空间里面去
优点适合海量数据因为一次性没有那么大空间装那么多数据我么可以借助辅助空间。 3 代码实现
这里的partitionOne函数和partitionTwo函数和partitionTreee函数效果一样我们用其中的一个就行了。
#include iostream
#include vectorusing namespace std;void swap(int* a, int* b)
{int temp *a;*a *b;*b temp;
}void printVector(vectorint v)
{for (int i 0; i v.size(); i){std::cout v[i] \t;}std::cout std::endl;
}/**partition算法 记得如果这里是C我们传递的是vector类型我们记得要加引用*不然改变不了数据这里和java传递ArrayList不一样ArrayList作为参数可以改变集合里面的值*所以C如果函数传递非基本数据类型一半都是带引用的*/
int partitionOne(vectorint vector, int start, int end)
{if (start end){std::cout vector is empty or start end std::endl;return -1;}int pivot vector[start];while (start end){//我们先从尾巴开始while (start end pivot vector[end]){--end;}//这里用的数组赋值而不是直接用swap交换函数那么下面的2步也是用数组赋值而不是用swap交换函数vector[start] vector[end];while (start end pivot vector[start]){start;}vector[end] vector[start];}//std:cout start is start end is end std::endl;vector[start] pivot;//printVector(vector);return start;
}/**partition算法, 这里只不过增加了2个变量i和j**/
int partitionTwo(vectorint vector, int start, int end)
{if (start end){return -1;}int i start;int j end;int pivot vector[start];while (i j){//我们先从尾巴开始while (i j pivot vector[j]){--j;}//这里用的数组赋值而不是直接用swap交换函数那么下面的2步也是用数组赋值而不是用swap交换函数vector[i] vector[j];while (i j pivot vector[i]){i;}vector[j] vector[i];}vector[i] pivot;//printVector(vector);// quickSort1(vector, start, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/// quickSort1(vector, i 1, end);return i;
}/**partition算法, 这里只不过增加了2个变量i和j,然后使用了交换函数swap**/
int partitionThree(vectorint vector, int start, int end)
{if (start end){return -1;}int i start;int j end;int pivot vector[start];while (i j){//我们先从尾巴开始while (i j pivot vector[j]){--j;}while (i j pivot vector[i]){i;}//这里用的shiswap交换函数那么下面的是是也是swap交换函数swap(vector[i], vector[j]);}swap(vector[i], vector[start]);//printVector(vector);return i;
}/***快速排序 调用第一个partitionOne*/
void quickSortOne(vectorint vector, int start, int end)
{if (vector.size() 0 || start end)return;int index partitionOne(vector, start, end);quickSortOne(vector, start, index - 1);quickSortOne(vector, index 1, end);
}/***快速排序 调用第二个partitionTwo */
void quickSortTwo(vectorint vector, int start, int end)
{if (vector.size() 0 || start end)return;int index partitionTwo(vector, start, end);quickSortTwo(vector, start, index - 1);quickSortTwo(vector, index 1, end);
}/***快速排序 调用第三个partitionThree*/
void quickSortThree(vectorint vector, int start, int end)
{if (vector.size() 0 || start end)return;int index partitionThree(vector, start, end);quickSortThree(vector, start, index - 1);quickSortThree(vector, index 1, end);
}/*** 得到数组里面最小的几个数*/
void getLeastNumber(vectorint input, int inputLen, vectorint output, int k)
{if (input.size() 0 || inputLen 0 || k inputLen || k 0){std::cout input size is zero or inputLen 0 or k inputLen or k 0 std::endl;return;}int start 0;int end inputLen - 1;int index partitionTwo(input, start, end);while (index ! k - 1){if (index k - 1){start index 1;index partitionTwo(input, start, end);}else{end index - 1;index partitionTwo(input, start, end);}}for (int i 0; i k; i){output.push_back(input[i]);}
}int main()
{vectorint v2;v2.push_back(6);v2.push_back(5);v2.push_back(1);v2.push_back(4);v2.push_back(2);v2.push_back(7);v2.push_back(3);v2.push_back(8);vectorint v3;getLeastNumber(v2, v2.size(), v3, 4);printVector(v3);return 0;
} 4 运行结果
2 1 3 4 5 借助辅助空间的赛选海量数据代码实现
#include iostream
#include vector
#include set
#include functionalusing namespace std;//typedef multisetint, greaterint intSet; 这样写错了中间还要一个空格
typedef multisetint, greaterint intSet;
typedef multisetint, greaterint ::iterator setIterator;void printSet(intSet set)
{setIterator iter set.begin();std::cout ---- std::endl;for (; iter ! set.end(); iter){std::cout value is *iter endl;} std::cout ---- std::endl;
}/*** 得到数组里面最小的几个数*/
void getLeastNumberOne(vectorint input, int inputLen, intSet output, int k)
{if (input.size() 0 || inputLen 0 || k inputLen || k 0){std::cout input size is zero or inputLen 0 or k inputLen or k 0 std::endl;return;}for (vectorint::iterator iter input.begin(); iter ! input.end(); iter){if (output.size() k) {output.insert(*iter);}else{setIterator setIter output.begin();if (*iter *setIter){//output.erase(*setIter)错错了//erase函数不是删除的指针值是删除的指针 output.erase(setIter);output.insert(*iter);}}}
}int main()
{vectorint v2;v2.push_back(6);v2.push_back(5);v2.push_back(1);v2.push_back(4);v2.push_back(2);v2.push_back(7);v2.push_back(3);v2.push_back(8);intSet v3;getLeastNumberOne(v2, v2.size(), v3, 4);setIterator iter v3.begin();for (; iter ! v3.end(); iter){std::cout value is *iter endl;}return 0;
} 6 运行结果
value is 4
value is 3
value is 2
value is 1 7 总结
如果看到了什么海量数据的话我么可以单独借助辅助空间然后辅助空间里面以以时间复杂度最小来进行删除、增加、查找操作。
