【Java -- 算法】数组算法（二）

一、前言

本文介绍了有关数组的算法第一部分的 Java 代码实现，算法实例：

• 找到最小的k个数
• 连续子数组的最大和
• 连续子数组的最大和（二维）
• 求数组当中的逆序对

二、代码 1. 找到最小的 k 个数

问题描述 即寻找一列数中最小的k个数

解决思路 利用最大堆的特点，加入我们对一个长度为N的数组p的前k个元素进行建堆操作，那么p[0]为p[0,…,k-1]的最大值，之后再对p[k,…,N-1]依次遍历：

• 如果p[i]小于p[0]，那么就说明它属于p[0,…,i]最小的K个元素之一，而p[0]则一定不属于p[0,…,N-1]的最小的k个元素，此时将p[i]和p[0]交换，重新对[0,…,N-1]的部分进行建堆操作
• 如果p[i]大于等于p[0]，那么就说明p[i]一定不属于p中最小的k个元素，因此忽略

直到i遍历到N-1为止，此时p[0,…,k-1]就是数组p最小的K个元素。

实现代码

class Untitled {
    
    static void maxHeapify(int p[], int di, int length){
        int li = (di