topK总结(初稿)

问题1 在n个有序数组中,求topK

假定有20个有序数组,每个数组有500个数字,降序排列,数字类型32位uint数值,现在需要取出这10000个数字中最大的500个

假如有n个数组升序, 每个数字长度是m 求这n个数组中(n*m) 最大的k个数

考察基础:两个有序数组合并

1.1 step 用最容易理解方式去做

两个数组两个数组比较

1 定义一个新的数组大小是TOP[k] 然后遍历n个数组 假如是第一个数组a[0],将最大的k个数 赋值给top[k] 2 假如是第二个数组a[1],将最大的k个数 和top[k] 进行比较 : 两个有序链表排序选出前k大 //伪代码 while(ib) {TOP[k]=a[n-i]} }

3 重复步骤2 直到遍历n个数组 TOP[k]记录就是结果

1.2优化

步骤2可用折半查找完成 gettopK

1.3分析:

时间复杂度:O(n^2) 数组两两比较获取结果 空间复杂度:O(m)

2 用最大堆堆排序:

竖向遍历 可参考基数排序 n有序链表合并成一个有序链表

  • 两个有序数组 分别取出 1个记录 累计2个变量, 很容易判读那个是最大的
  • n个数组,分别取出1个记录 累计n个变量,这有相当于有形成一个新的数组,要求是获取最大的一个。 heap排序 priority_queue具备这个特性

步骤 2.1 step:

  1. 建立大顶堆,维度为数组的个数,这里为20(第一次 插入的是每个数组中最大的值,即第一个元素)。
  2. 删除最大堆堆顶,保存到数组或者栈中,然后向最大堆插入删除的元素所在数组的下一个元素。
  3. 重复第1,2个步骤,直到删除个数为最大的K个数,这里为500.

2.2

时间复杂度:O(nlogn) 减少比较次数 n为外围循环 logn调整一次时间 空间复杂度:heap O(n)

2.3 对比

和归并排序对比 heap减少占用更少空间 只需要大小为n的数组 因为归并需要完全排序完毕才 只需要大小为n×m的数组

归并排序需要把待排数据全部存储内存中

问题2 海量数据处理的 Top K算法(问题)

问题描述:  有N(N>>10000)个整数,求出其中的前K个 最大的数。

最小堆 每次有数据输入的时候可以先与根节点比较

  • 若不大于根节点,则舍弃
  • 否则用新数值替换根节点数值, 并进行最小堆的调整

扩展思考:

假如要对一个很大记录的文件进行全部排序呢? 回答: 利用B+思想 大文件拆分整体有序小文件

考点: 题目要求最大的k个数 不要求全部排序

问题3 一个无顺数组中求top K

问题 4 判读是否存在重复

A Bloom Filter is a probabilistic data structure that is used to test whether an element is a member of a set, or more simply,

instead of storing each value, a bloom filter is simply an array of bits indicating the presence of that key in the filter

参考

1 http://www.cnblogs.com/ywl925/p/3794852.html 2 http://blog.csdn.net/collonn/article/details/19039931

3 http://blog.csdn.net/gzxcyy/article/details/13510995 4 http://www.cnblogs.com/xudong-bupt/archive/2013/03/20/2971262.html 5 http://blog.csdn.net/v_july_v/article/details/7382693

7 https://en.wikipedia.org/wiki/Bloom_filter 8 instead of storing each value https://www.igvita.com/2008/12/27/scalable-datasets-bloom-filters-in-ruby/

原文发布于微信公众号 - 架构说(JiaGouS)

原文发表时间:2016-06-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

C/C++数据类型的转换之终极无惑

数据类型在编程中经常遇到,虽然可能存在风险,但我们却乐此不疲的进行数据类型的转换。

1023
来自专栏Java架构师进阶

Java 常见的 30 个误区与细节!

1、在Java中,没有goto语句。因为大量使用goto语句会降低程序的可读性和可维护性,所以Java语言取消了goto的使用。同时,为了避免程序员自行使用go...

863
来自专栏老马说编程

(29) 剖析String / 计算机程序的思维逻辑

上节介绍了单个字符的封装类Character,本节介绍字符串类。字符串操作大概是计算机程序中最常见的操作了,Java中表示字符串的类是String,本节就来详细...

2015
来自专栏前端桃园

[第 3 期]JavaScript数据结构之数组栈队列

1485
来自专栏java工会

2018年百度大神讲解 JAVA基础知识解析(重点)

2283
来自专栏Vamei实验室

Python进阶04 函数的参数对应

我们已经接触过函数(function)的参数(arguments)传递。当时我们根据位置,传递对应的参数。我们将接触更多的参数传递方式。 回忆一下位置传递: d...

2037
来自专栏Java编程

Java基础—String、StringBuffer、StringBuilder

我有一个微信公众号,经常会分享一些Java技术相关的干货。如果你喜欢我的分享,可以用微信搜索“Java团长”或者“javatuanzhang”关注。

3880
来自专栏CoXie带你学编程

详解Python 2.x 与 Python 3.x 的区别

如果你是刚接触 Python 的初学者,那你可能是直接学习 Python 3.x 版本。对于 Python 2.x 的版本是不会有所接触。官方也宣布在 2020...

2122
来自专栏一“技”之长

Swift解读专题一——Swift2.2语言预览

        本系列专题是我通过阅读Swift2.2语言开发文档,翻译总结加上自己的理解整理而成。其中大部分结构和内容都来自开发文档,有疏漏和错误之处,还望更...

992
来自专栏Golang语言社区

【Golang语言社区】JS基础-javascript 特殊的面向对象以及继承详解(入门篇)

学习Javascript人,大多听说一句话叫js里面一切都是对象。我刚开始接触javascript面向对象编程时候,挺乱的,我当时习惯性的把PHP的面像对象思想...

3868

扫码关注云+社区

领取腾讯云代金券