前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >TopN问题

TopN问题

作者头像
搬砖俱乐部
发布2020-01-17 15:41:50
4370
发布2020-01-17 15:41:50
举报
文章被收录于专栏:BanzClub

问题1-1:给定一个数字数组,求出出现频率最高的K个数字;

代码语言:javascript
复制
// 堆排序
public List<Integer> topKFrequent(int[] nums, int k) {
        //  时间复杂度:O(n)
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    // 时间复杂度:O(n) * O(logn)
    PriorityQueue<Integer> queue = new PriorityQueue<>(nums.length, (o1, o2) -> map.get(o1) - map.get(o2));
    for (Integer key : map.keySet()) {
        queue.add(key);
        if (queue.size() > k) {
            queue.poll();
        }
    }

    // 时间复杂度:O(k)
    List<Integer> result = new LinkedList<>();
    while (!queue.isEmpty()) {
        result.add(queue.poll());
    }

    // 时间复杂度:O(k)
    Collections.reverse(result);
    return result;
}

// 桶排序
public List<Integer> topKFrequent(int[] nums, int k) {
    //  时间复杂度:O(n)
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    // 时间复杂度:O(n)
    List<Integer>[] buckets = new List[nums.length + 1];
    for (Integer key : map.keySet()) {
        int i = map.get(key);
        if (buckets[i] == null) {
            buckets[i] = new ArrayList<>();
        }
        buckets[i].add(key);
    }

    // 时间复杂度:O(n)
    List<Integer> result = new LinkedList<>();
    for (int i = buckets.length - 1; i > 0; i--) {
        if (buckets[i] == null) {
            continue;
        }
        for (Integer value : buckets[i]) {
            if (result.size() >= k) {
                return result;
            }
            result.add(value);
        }
    }
    return result;
}

问题1-2:给定一个单词列表,求出单词出现频率K个,相同频率,字母序排序;

代码语言:javascript
复制
// Java 桶排序
public List<String> topKFrequent(String[] words, int k) {

    //  时间复杂度:O(n)
    Map<String, Integer> map = new HashMap<>();
    for (String word : words) {
        map.put(word, map.getOrDefault(word, 0) + 1);
    }

    PriorityQueue<String>[] buckets = new PriorityQueue[words.length + 1];
    for (String key : map.keySet()) {
        int i = map.get(key);
        if (buckets[i] == null) {
            buckets[i] = new PriorityQueue();
        }
        buckets[i].add(key);
    }

    // 时间复杂度:O(n)
    List<String> result = new LinkedList<>();
    for (int i = buckets.length - 1; i > 0; i--) {
        if (buckets[i] == null) {
            continue;
        }
        while (!buckets[i].isEmpty()) {
            if (result.size() >= k) {
                return result;
            }
            result.add(buckets[i].poll());
        }
    }

    return result;
}

// Scala(MapReduce思想,效率不高)
def topKFrequent(words: Array[String], k: Int): List[String] = {
    val result = words.map((_, 1))
                                 .groupBy(_._1)
                                 .map(x => (x._1, x._2.size)).toList
                                 .sortWith((x, y) => x._2 > y._2 || (x._2 == y._2 && x._1 < y._1)).take(k)
                                 .map(_._1)
    result
}

问题2:从十亿数据中,找出最大的前K个数;

  • 分治、并行计算
  • 排序算法

串行版本:

建一个K个数的最小堆,与堆顶比较,大于(等于)堆顶,依次插入堆,超过K个数,踢出堆顶

并行版本:

  • 分成几份,分别求前K个数,可以多线程并行计算每份数据
  • 取每份数据的前K,组成新的集合,再计算前K个数

问题3:给定一个800G的nginx访问日志文件,2G内存,取出访问频率在top100的IP;

1、切分文件处理方式

  • 计算每行文件大概大小,按照每份数据大约2G来分文件,通常是按照换行符来切分;
  • 可以使用正则提取每行的IP,进行统计每个IP的访问次数;
  • 求出每个文件的Top100;
  • 再合并每个文件的Top100,再计算Top100即可;

2、MapReduce

  • Map提取Ip,统计访问个数
  • 自定义分区,相同Ip分到同一个task
  • TasK进行按照每个IP统计汇总
  • 再重新开启MapReduce读取每个统计好的文件
  • MapTask任务中,设置一个公共堆,大小为100,将每个ip的频率进行插入堆中,最小的将被丢弃掉,结束后统计出每个文件的top100
  • 使用一个ReduceTask进行一次求topN即可

3、Hive

  • RANK、DENSE_RANK、ROW_NUMBER

  • https://leetcode-cn.com/problems/top-k-frequent-elements/
  • https://leetcode-cn.com/problems/top-k-frequent-words/
  • 桶排序
  • 堆排序
  • 快速排序
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-01-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 BanzClub 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
GPU 云服务器
GPU 云服务器(Cloud GPU Service,GPU)是提供 GPU 算力的弹性计算服务,具有超强的并行计算能力,作为 IaaS 层的尖兵利器,服务于生成式AI,自动驾驶,深度学习训练、科学计算、图形图像处理、视频编解码等场景。腾讯云随时提供触手可得的算力,有效缓解您的计算压力,提升业务效率与竞争力。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档