【经典面试题目】--从1百万(一亿)的数据中找top100大的数

2024-01-16 01:04

本文主要是介绍【经典面试题目】--从1百万(一亿)的数据中找top100大的数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 概述
    • 下面我们看具体方法:
      • 方法一:基于quicksort实现的原理如下
      • 方法二:minHeap(小顶堆实现)
    • 问题
    • 总结:

概述

一种做法是我们直接进行一个堆排序,或者快排,然后打印前100个即可,但是这样子比较耗时间;
平均下来快排都在9000多ms,而堆排就更大,32s多;所以我们不能简单粗暴的直接快排或者堆排,要对其进行相对的优化;(这种做法不可取,要优化!!!)


下面我们看具体方法:

方法一:基于quicksort实现的原理如下

(ps:前提是快排是要懂得,不懂得可以请各位移步去看我这一篇博文:快速排序)

1. 假设数组为 array[N] (N = 1 亿),首先利用一次quicksort的原理把array分成两个部分,左边部分比基准值大, 右边部分比基准小。 得到基准值在整个数组中的位置,假设是 k.
2. 如果 k 比 99 大,原数组变成了 array [0, ...  k - 1], 然后在数组里找前 100 最大值。 (继续递归)
3. 如果 k 比 99 小, 原数组变成了 array [k + 1, ..., N ], 然后在数组里找前 100 - (k + 1) 最大值。(继续递归)
4. 如果 k == 99, 那么数组的前 100 个值一定是最大的。(退出)

代码部分:

//找出一亿数据里面的前100个  快排思路
//先进行一次快排  找到基准值排序后的位置 start,使得左边数全部大于它,右边数全部小于它
//然后对比 start与99的大小 因为数组从0开始的所以对比99
//  start>99的话,就从arr[0,start-1] 中找前100个最大的、
//  start<99的话,就从arr[start+1,end] 中找前100-(start+1)个最大的
//  start==99的话,那么数组的前 100 个值一定是最大的 (不用排序直接返回 因为只是要前100最大的,没有要求说对这100个数再进行排序)
public class FastTake100 {public static void quickSort(int[] arr, int left, int right, int k) {//1.一次快排找出基准值最后的位置:startif (left >= right) {return;}int start = left;int end = right;int num = arr[left];//以最左边为基准值while (start < end) {while (start < end && num >= arr[end]) {end--;}while (start < end && num <= arr[start]) {start++;}if (start < end) {int temp = arr[start];arr[start] = arr[end];arr[end] = temp;}}arr[left] = arr[start];arr[start] = num;//2.进行判断 然后继续递归if (start < k - 1) {//start<99的话,就从arr[start+1,right] 中找前100-(start+1)个最大的quickSort(arr, start + 1, right, k - start - 1);} else if (start > k - 1) {//start>99的话,就从arr[0,start-1] 中找前100个最大的quickSort(arr, 0, start - 1, k);} else {//start==99的话,那么数组的前 100 个值一定是最大的 直接返回即可return;}}public static void main(String[] args) {int[] arr = new int[100000000];for (int i = 0; i < arr.length; i++) {arr[i] = (int) (Math.random() * 100000000);}int k = 100;//开始时间long one = System.currentTimeMillis();quickSort(arr, 0, arr.length - 1, k);//结束时间long two = System.currentTimeMillis();//打印耗时System.out.println(two - one);//打印top100for (int i = 0; i < 100; i++) {System.out.println(arr[i]);}}
}

总结: 基于quicksort原理的方法运行时间不稳定(每次运行时间相差大);不管是固定中枢轴,还是中枢轴采用三数取中法,每次运行时间差距都挺大,30ms-1000ms不等。


方法二:minHeap(小顶堆实现)

最大堆 max-heap(大顶堆):每个节点的键值(key)都大于或等于其子节点键值
最小堆 min-heap(小顶堆):每个节点的键值(key)都小于或等于其子节点键值

# 当前节点 i:1.则其父节点: i/2 (因为/默认就是向下取整)或者(i-1) /22.两个孩子节点:2i+1;  2i+2;

有些小伙伴可能想到,既然是找top100,为什么不是用大顶堆来实现,而是用小顶堆呢?
在写之前,我也有这样的想法,带着疑惑我们来看下面的分析:
(ps:前提是堆排序是要懂得,不懂得可以请各位移步去看我这一篇博文:堆排序实现)

知道堆排序的具体步骤以及相应的代码已经看懂,会自己写出来后,我们来看看本题的分析:

  1. 先new一个100大小的数组 value[100];
  2. 然后我们直接把原始数组arr的前100个数初始化给value;(看清楚哦,前100个数是指:是0-99的下标的值,这里不对arr进行堆排序);
  3. 把value数组,进行小顶堆化,这样堆顶的元素value[0]就是最小的;
  4. 核心:我们 设 i 从k开始,到arr的长度结束;每次比较value[0]与arr[i]的的大小,只要arr[i] > value[0] ,我们就把arr[i] 赋值给value[0],此时堆顶元素就是一个比较大的元素,然后我们重新进行一次heapify(小顶堆化),再把堆顶置于最小,继续与arr[i]比较,重复上述过程直到遍历完整个arr数组;(每次都会把最小的元素替换掉)
  5. 遍历完以后,我们的value数组里存的就是 top100大的数字了;
  6. 打印value数组,就可以看到结果;

下面看代码:

import java.util.Random;
找出一亿数据里面的前100个  堆排思路 利用minHeap 小顶堆
public class HeapTake100 {public static int[] heapSort(int[] arr) {//new 一个数组存储top100的元素int[] value=new int[100];//初始化value数组for (int i = 0; i < 100; i++) {value[i]=arr[i];}//把value数组构建成小顶堆buildHeap(value);for (int i = 100; i <arr.length ; i++) {//若满足条件就赋值if (value[0]<arr[i]){value[0]=arr[i];//重新小顶堆化heapify(value,0,value.length);}}return value;}//从第一个非叶子节点开始 往上遍历建立堆public static void buildHeap(int[] arr) {//数组的长度/2 - 1 就是:第一个非零节点的位置int n=arr.length;for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, i, n);}}//heapify 真正用来调整堆的方法public static void heapify(int[] arr, int i, int len) {int left = 2 * i + 1;int right = 2 * i + 2;int max = i;if (left < len && arr[left] < arr[max]) {max = left;}if (right < len && arr[right] < arr[max]) {max = right;}if (max != i) {swap(arr, max, i);heapify(arr, max, len);}}//堆排序用来交换的方法public static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}//执行的主函数public static void main(String[] args) {int[] arr = new int[100000000];for (int i = 0; i < arr.length; i++) {arr[i] = (int) (Math.random() * 100000000);}//计算消耗时间long t1=System.currentTimeMillis();int[] value=heapSort(arr);long t2=System.currentTimeMillis();System.out.println(t2-t1);//打印结果数组for (int i : value) {System.out.println(i);}}
}

问题


那么又有人问了:为什么不用大顶堆?

假如使用大顶堆,当value[0] < arr[i] 时候,我们替换,会发现value[0] 始终是整个堆里最大的,这样子操作,只是每次把value[0] 换了一个最大的,也就是最后只找到 top1大的元素;

-------当然实践出真知,各位可以自己去动手尝试一下写,然后看看要是改成大顶堆,每次用大顶堆最后一个元素进行比较交换,看看会会出现什么样的结果。

总结:

基于最小堆方法运行时间很稳定(每次运行时间相差很小 基本都是52ms左右);

这篇关于【经典面试题目】--从1百万(一亿)的数据中找top100大的数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/610825

相关文章

Pandas统计每行数据中的空值的方法示例

《Pandas统计每行数据中的空值的方法示例》处理缺失数据(NaN值)是一个非常常见的问题,本文主要介绍了Pandas统计每行数据中的空值的方法示例,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是空值?为什么要统计空值?准备工作创建示例数据统计每行空值数量进一步分析www.chinasem.cn处

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

Spring 请求之传递 JSON 数据的操作方法

《Spring请求之传递JSON数据的操作方法》JSON就是一种数据格式,有自己的格式和语法,使用文本表示一个对象或数组的信息,因此JSON本质是字符串,主要负责在不同的语言中数据传递和交换,这... 目录jsON 概念JSON 语法JSON 的语法JSON 的两种结构JSON 字符串和 Java 对象互转

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

数据库面试必备之MySQL中的乐观锁与悲观锁

《数据库面试必备之MySQL中的乐观锁与悲观锁》:本文主要介绍数据库面试必备之MySQL中乐观锁与悲观锁的相关资料,乐观锁适用于读多写少的场景,通过版本号检查避免冲突,而悲观锁适用于写多读少且对数... 目录一、引言二、乐观锁(一)原理(二)应用场景(三)示例代码三、悲观锁(一)原理(二)应用场景(三)示例

SpringBoot集成Milvus实现数据增删改查功能

《SpringBoot集成Milvus实现数据增删改查功能》milvus支持的语言比较多,支持python,Java,Go,node等开发语言,本文主要介绍如何使用Java语言,采用springboo... 目录1、Milvus基本概念2、添加maven依赖3、配置yml文件4、创建MilvusClient

SpringValidation数据校验之约束注解与分组校验方式

《SpringValidation数据校验之约束注解与分组校验方式》本文将深入探讨SpringValidation的核心功能,帮助开发者掌握约束注解的使用技巧和分组校验的高级应用,从而构建更加健壮和可... 目录引言一、Spring Validation基础架构1.1 jsR-380标准与Spring整合1

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

SpringBatch数据写入实现

《SpringBatch数据写入实现》SpringBatch通过ItemWriter接口及其丰富的实现,提供了强大的数据写入能力,本文主要介绍了SpringBatch数据写入实现,具有一定的参考价值,... 目录python引言一、ItemWriter核心概念二、数据库写入实现三、文件写入实现四、多目标写入