寻找大数组第k大元素时遭遇OutOfMemoryError问题求助

可能的内存泄漏/过度占用点及排查方案 #

1. FastReader的输入缓存问题
   很多自定义FastReader会一次性读取整行甚至全部输入到内存中（比如用readLine()读取包含500万数字的行，或者把整个输入流转成字符串）。这种情况下，单一行的字符串内存占用可能轻松超过几十MB，直接触发OOM。

   • 优化方案：改成逐字符流式解析数字，避免读取整行或缓存全部输入。示例实现：

     class FastReader {
         private BufferedReader br;
     
         public FastReader() {
             br = new BufferedReader(new InputStreamReader(System.in));
         }
     
         public int nextInt() throws IOException {
             int c = br.read();
             // 跳过空白字符
             while (c <= ' ') {
                 c = br.read();
             }
             int sign = 1;
             if (c == '-') {
                 sign = -1;
                 c = br.read();
             }
             int num = 0;
             while (c > ' ') {
                 num = num * 10 + (c - '0');
                 c = br.read();
             }
             return num * sign;
         }
     }
     

     这种方式不会缓存整行数据，内存占用仅维持在单个数字解析的临时变量级别。

2. k值过大时的临时数组开销
   虽然你用了长度为k的数组，但如果k接近500万（比如找第499万大的元素），这个数组本身会占用约20MB（int类型）或40MB（long类型）内存。如果平台JVM堆内存默认限制较低，再加上其他隐性开销，就可能触发OOM。

   • 优化方案：针对极端k值做特殊处理：
     • 当k == 1：直接遍历输入记录最大值，无需创建临时数组；
     • 当k == n：直接遍历输入记录最小值，无需维护前k个元素；
     • 当k > n/2：转换为找第n - k + 1小的元素，缩小临时数组的长度。

3. 最小值查找逻辑的额外内存开销
   如果你在找临时数组最小值时，使用了排序、创建辅助数组或迭代器等操作，会产生额外的内存占用。比如每次找最小值都复制数组再排序，500万次循环下来，内存会持续堆积。

   • 优化方案：直接遍历临时数组找最小值索引，无额外内存开销：

     private int findMinIdx(int[] temp) {
         int minIdx = 0;
         for (int i = 1; i < temp.length; i++) {
             if (temp[i] < temp[minIdx]) {
                 minIdx = i;
             }
         }
         return minIdx;
     }
     

4. 循环内的临时对象堆积
   如果在循环中频繁创建String、Integer包装类等对象（比如用StringTokenizer的nextToken()生成大量字符串），500万次循环会产生数百万个对象，导致垃圾回收不及时，内存溢出。

   • 优化方案：使用基本类型（int而非Integer），避免不必要的对象创建，比如前面的逐字符解析数字就不会生成额外的String对象。

排查步骤总结 #

1. 优先检查FastReader的输入处理逻辑，确保没有大内存缓存；
2. 针对k的极端取值做特殊优化，避免创建过大的临时数组；
3. 确认最小值查找逻辑无额外内存开销；
4. 替换循环内的包装类/字符串对象为基本类型操作。

内容的提问来源于stack exchange，提问作者user18512699