N 个无序数中找出最大的 M 个数

2018-03-30

实现思路：新建一个拥有 M 个元素的数组 Find，将 N 个数中的前 M 个元素存入该数组，假设这前 M 个元素就是最大值，在存入的过程中找出最小数值的索引 minIndex。然后从 N 个数中的第 ( M + 1 ) 个元素开始，逐个与 Find 数组中的最小值进行比较，若大于 Find 数组中的最小值，则将其替换。替换完毕后，继续循环找出 Find 数组中最小值的索引，外层的 while 在进行下一次循环时，会直接拿 N 的下一个元素与 Find 数组中的最小值进行比较。这样循环一遍之后，Find 数组中的最小值都被较大的数值替换，这时 Find 中存放的元素就是 N 中最大的 M 个数，这种思路的时间复杂度为O(n*logm)。这种实现方式可以将亿级数据量的运算时间控制在 100 毫秒内。

package com.sunzn.max;

import java.util.Random;

public class FindMax {

    public static void main(String[] args) {

        Random random = new Random();

        int n = 100000000;

        int[] Pool = new int[n];

        for (int i = 0; i < n; i++) {
            Pool[i] = random.nextInt(n);
        }

        findMax(Pool, 10);

    }

    private static void findMax(int[] data, int m) {

        long sTime = System.currentTimeMillis();

        int[] Find = new int[m];

        int minIndex = 0;

        for (int i = 0; i < Find.length; i++) {
            Find[i] = data[i];
            if (Find[minIndex] > Find[i]) {
                minIndex = i;
            }
        }

        while (m < data.length) {
            if (data[m] > Find[minIndex]) {
                Find[minIndex] = data[m];
                for (int i = 0; i < Find.length; i++) {
                    if (Find[minIndex] > Find[i]) {
                        minIndex = i;
                    }
                }
            }
            m++;
        }

        for (int i = 0; i < Find.length; i++) {
            System.out.printf("结果数据:");
            System.out.printf("%d", Find[i]);
            System.out.printf("\n");
        }

        long eTime = System.currentTimeMillis();

        System.out.printf("消耗时间:" + (eTime - sTime) + "毫秒");

    }

}

以下是运行结果，该结果是从拥有一亿个随机数的数组中寻找出来的，耗时 91 毫秒。

结果数据:99999998
结果数据:99999991
结果数据:99999993
结果数据:99999992
结果数据:99999996
结果数据:99999993
结果数据:99999991
结果数据:99999993
结果数据:99999994
结果数据:99999995
消耗时间:91毫秒

需要注意的是，基础数据量不能过大，否则会导致内存溢出。下面是将随机数从一亿增至十亿的时候导致的堆内存溢出，程序在创建数组阶段就奔溃了。

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at com.sunzn.max.FindMax.main(FindMax.java:13)
    
    int[] Pool = new int[n];