怎样将随机生成的十个数将数组a的值赋值给数组b为a？

来源：蜘蛛抓取(WebSpider) 时间：2019-10-26 06:32 标签： a复制b

（2）请在划线处填入合适的代码

km = "物理化学生物政治历史地理技术"

    好久没有写博客了这一段时间主要在准备为将来找工作复习，今天我就总结一下关于如何查找数组的前K个最小值实现方法查找前K个最小值实现方法很多，主要的思想包括如下的几种：

    1、对数组进行排序然后前K个元素就是需要查找的元素，排序的方法可以采用快速排序但是我们知道在快速排序中如果已经是有序的数组，采用快速排序的时间复杂度是O(N^2),为了解决这种问题通常选择随机选择一个数组值pivot作为基准，将数组分为S1 = pivot这样就能避免快速排序中存在的问题，或者采用随机选择三个元素然后取中间值作为基准就能避免快速算法的最差时间复杂度，这种方法的前K个數字是有序的

2、既然是选择前K个对象，那么就没必要对所有的对象进行排序可以采用快速选择的思想获得前K个对象，比如首先采用快速排序的集合划分方法划分集合：S1pivot，S2然后比较K是否小于S1的个数，如何小于则直接对S1进行快速排序，如果K的个数超过S1,那么对S2进行快速排序排序完成之后，取数组的前K个元素就是数组的前K个最小值这种实现方法肯定比第一种的全快速排序要更快速。

3、将数组转换为最尛堆的情况根据最小堆的特性，第一个元素肯定就是数组中的最小值这时候我们可以将元素保存起来，然后将最后一个元素提升到第┅个元素重新构建最小堆，这样进行K次的最小堆创建就找到了前K个最小值，这是运用了最小堆的特性实质上是最小堆的删除实现方法。这种算法的好处是实现了数组的原地排序并不需要额外的内存空间。

4、接下来的这种思想有点类似桶排序首先给定一个K个大小的數组b，然后复制数组a中的前K个数到数组b中将这K个数当成数组a的前K个最小值，对数组b创建最大堆这时候再次比较数组a中的其他元素，如果其他元素小于数组b的最大值（堆顶）则将堆顶的值进行替换，并重新创建最大堆这样遍历一次数组就找到了前K个最小元素。这种方法运用了额外的内存空间特别当选择的K值比较大时，这种方法有待于权衡一下

    这种方法对于海量数据来说是有较好的作用，对于海量數据不能全部存放在内存中这时候创建一个较小的数组空间，然后创建最大堆从硬盘中读取其他的数据，进而实现前K个数据的查找

    這是比较传统的几种方法，当然还存在其他的选择方式我在这边就不阐述了，从上面几种方法的可知查找方法都充分运用了运用了数據结构和算法的特性。因此数据结构的灵活运用对算法的实现有很多的好处

下面是我的实现代码，数组中前K个元素我通过打印的方式实現并没有保存到新的数组中：

点击(此处)折叠或打开
































  32. /*采用快速排序查找*/





  38. /*采用快速选择实现*/





  44. /*采用最大堆实现*/







  52. /*采用最小堆删除元素的方式实现*/














點击(此处)折叠或打开

从结果可知，快速排序的算法效果最差而最大堆的效果最好，最小堆的效果其次但是最大堆运用了额外的内存空間。因此在内存空间限制的情况下考虑最小堆是比较合适的。但是最大堆的思想确实很精妙的运用了类似桶排序的性质。

为了说明算法能否实现前K个最小值的查找改变数组大小为50，并打印各个方法完成的情况查找前10个数据，实验结果如下所示：

点击(此处)折叠或打开

從上面的实验结果可知四种方法都是实现了获得前K个最小元素。

我要回帖

更多关于 a复制b 的文章

 

随机推荐