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

发布时间:2024年01月15日

概述

一种做法是我们直接进行一个堆排序,或者快排,然后打印前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.一次快排找出基准值最后的位置:start
        if (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);
        //打印top100
        for (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左右);

文章来源:https://blog.csdn.net/m0_48904153/article/details/135612439
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。