一、概要
本文介绍了有关数组的算法第二部分的Java代码实现，所有代码均可通过 直接运行，算法目录：
- 找到最小的
k个数 - 连续子数组的最大和
- 连续子数组的最大和（二维）
- 求数组当中的逆序对
二、代码实现
2.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<<1)+1; int t = p[di]; while (li < length) { if (li+1 < length && p[li+1] > p[li]) li++; if (p[di] >= p[li]) break; p[di] = p[li]; di = li; li = (di<<1)+1; } p[di] = t; } static void buildMaxHeap(int p[], int length){ for(int i=(length>>1)-1; i >= 0; i--){ maxHeapify(p, i, length); } } static void minKthNum(int p[] ,int k, int length) { buildMaxHeap(p,k); int t; for (int i=k; i < length; i++) { if (p[i] < p[0]) { t = p[0]; p[0] = p[i]; p[i] = t; maxHeapify(p, 0, k); } } } public static void main(String[] args) { int p[] = new int[]{ 2, 3, 10, 2, 5, 6, 7, 20, 1, -5}; minKthNum(p, 3, p.length); for (int i=0; i < 3; i++) { System.out.println(String.valueOf(p[i])); } }}复制代码 运行结果
>> 2>> 1>> -5复制代码
2.2 连续字数组的最大和
问题描述
数组中的元素有正有负，在该数组中找出一个连续子数组，要求该连续子数组中各元素的和最大，这个连续子数组便被称作最大连续子数组。比如数组{2,4,-7,5,2,-1,2,-4,3}的最大连续子数组为{5,2,-1,2}，最大连续子数组的和为5+2-1+2=8。
解决思路
通过对数组中的元素进行线性的遍历，并对每个元素进行累加，当发现目前为止累加的和maxendinghere小于0时，则说明最大的连续子数组不可能包含目前遍历到的子数组，那么就从下一个元素tmaxbegin开始计算子数组。
在遍历的过程中更新目前位置获得的最大连续子数组的和maxsofar，以及起止位置maxbegin和maxend。
代码实现
class Untitled { static void maxSumSubArray(int p[], int length){ int maxendinghere = 0; int maxsofar = 0; int maxbegin = 0; int maxend = 0; int tmaxbegin = 0; //从0开始遍历数组。 for(int i = 0; i < length; i++){ //maxendinghere 记录当前计算子数组的和。 maxendinghere += p[i]; //如果该和小于0，那么重新计算。 if(maxendinghere < 0){ maxendinghere = 0; tmaxbegin = i+1; } //更新目前为止计算到的最大值。 if(maxsofar < maxendinghere){ maxbegin = tmaxbegin; maxend = i; maxsofar = maxendinghere; } } //考虑数组全部是负数的情况 if(maxsofar == 0){ maxsofar = p[0]; for(int i = 1; i < length; i++){ if(p[i] > maxsofar){ maxsofar = p[i]; maxbegin = i; maxend = i; } } } for (int i = maxbegin; i <= maxend; i++) { System.out.println("i=" + p[i]); } } public static void main(String[] args) { int p[] = new int[]{ 2,4,-7,5,2,-1,2,-4,3}; maxSumSubArray(p, p.length); }}复制代码 运行结果
> i=5> i=2> i=-1> i=2复制代码
2.3 连续子数组的最大和（二维）
问题描述
这个问题其实是2.2的变种，这时候输入是一个二维的矩阵，需要找到一个子矩阵，该子矩阵的和是这个二维的所有子矩阵中最大的。
解决思路
二维的问题和2.2中的一维问题的核心解决思路相同。
对于二维情况，我们将 同一列的多个元素合并成一个元素 来实现降维的效果，为了能实现在O(1)的时间内计算出同一列的多行元素之和，需要构建一个辅助数组，该辅助数组ps[i][j]的值，等于原输入数组p以p[0][0]为左上角到p[i][j]为右下角构成的子矩阵的所有元素之和，通过该辅助数组就能在O(1)的时间内计算出lRow到hRow行之间第col列的所有元素之和，计算公式为：
ps[hRow][col] - ps[hRow][col-1] - ps[lRow-1][col] + ps[lRow-1][col-1]复制代码
代码实现
class Untitled { //计算从lRow到hRow之间，位于第col列的所有元素之和。 static int getColsum(int ps[][], int lRow, int hRow, int col) { return ps[hRow][col] - ps[hRow][col-1] - ps[lRow-1][col] + ps[lRow-1][col-1]; } static void maxSumSubArray2(int p[][], int xlen, int ylen){ int maxendinghere = 0; int maxsofar = 0; int tColbegin = 1; int sx = 0; int sy = 0; int ex = 0; int ey = 0; //初始化辅助数组，ps[i][j]为以其为右下角的子矩阵的所有元素之和。 int psxLen = xlen+1; int psyLen = ylen+1; int[][] ps = new int[psxLen][psyLen]; for (int j = 0; j < psyLen; j++) ps[0][j] = 0; for (int i = 0; i < psxLen; i++) ps[i][0] = 0; for (int i = 1; i < psxLen; i++) { for(int j = 1; j < psyLen; j++) { ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + p[i-1][j-1]; } } //求矩阵中的最大和，将位于同一个列的多行元素合并成一个元素，因此需要遍历包含不同行的情况。 for (int pStartRow = 1; pStartRow < psxLen; pStartRow++) { for (int pEndRow = pStartRow; pEndRow < psxLen; pEndRow++) { for (int pCol = 1; pCol < psyLen; pCol++) { maxendinghere += getColsum(ps, pStartRow, pEndRow, pCol); if (maxendinghere < 0) { maxendinghere = 0; tColbegin = pCol+1; } if (maxsofar < maxendinghere) { maxsofar = maxendinghere; sx = pStartRow - 1; sy = tColbegin - 1; ex = pEndRow - 1; ey = pCol - 1; } } maxendinghere = 0; tColbegin = 1; } } System.out.println("最大和=" + maxsofar + ",起始行=" + sx + ",终止行=" + ex + ",起始列=" + sy + ",终止列=" + ey); } public static void main(String[] args) { int[][] p = { { 1,-10,-11}, { 4,5,6}, { 7,8,9}}; maxSumSubArray2(p, 3, 3); }}复制代码 运行结果
>> 最大和=39,起始行=1,终止行=2,起始列=0,终止列=2复制代码
2.4 求数组中的逆序对
问题描述
在数组中的两个数字，如果 前面一个数字大于后面的数字，则这两个数字组成一个 逆序对。输入一个数组，求出这个数组中的逆序对的总数。
解决思路
这里采用的是 归并算法 的思想，归并算法包含三个关键步骤：
- 分解：把长度为
n的待排序列分解成两个长度为n/2的序列。 - 治理：对每个子序列分别调用归并排序，进行递归操作。当子序列长度为
1时，序列本身有序，停止递归。 - 合并：合并每个排序好的子序列。
对于上面的例子，我们将整个数组分解为A、B两部分，则整个数组的逆序对个数就等于：
A部分组成的数组的逆序对 + B部分组成的数组的逆序对 + A与B之间的逆序对复制代码
这里有一个关键的点，就是需要保证在计算A与B之间的逆序对时，A和B内的元素都是有序的。
class Untitled { static int inversePairs(int p[], int startIndex, int endIndex) { if (endIndex == startIndex) { return 0; } if (endIndex-startIndex == 1) { if (p[endIndex] < p[startIndex]) { int temp = p[startIndex]; p[startIndex] = p[endIndex]; p[endIndex] = temp; return 1; } else { return 0; } } int midOffset = (endIndex-startIndex) >> 1; int l = inversePairs(p, startIndex, startIndex+midOffset); int r = inversePairs(p, startIndex+midOffset+1, endIndex); return l + r + inverseCore(p, startIndex, midOffset, endIndex); } static int inverseCore(int p[], int startIndex, int midOffset, int endIndex) { int totalLen = endIndex-startIndex+1; int lLen = midOffset+1; int rLen = totalLen-lLen; int l[] = new int[lLen+1]; int r[] = new int[rLen+1]; int i = 0; for (i=0; i << 30; for (i=0; i << 30; int c = 0; i = 0; int m = 0; int n = 0; while(i < totalLen) { if (r[n] <= l[m]) { p[startIndex+i] = r[n]; c += (lLen - m); n++; i++; } else { p[startIndex+i] = l[m]; m++; i++; } } return c; } public static void main(String[] args) { int[] p = { 7,5,6,4}; System.out.println("Inverse Count=" + inversePairs(p, 0, 3)); }}复制代码 运行结果
>> Inverse Count=5复制代码
更多文章，欢迎访问我的 Android 知识梳理系列：
- Android 知识梳理目录：
- Android 面试文档分享：