0°

面试算法知识梳理五:数组第二部分

内容预览:
  • 人生须有四种经历,耐得住寂寞,经得起考验,承受了压力,面对了孤独~
  • 代码实现 class Untitled {    static void maxHeapify(int p...~
  •    static int getColsum(int ps为以其为右下角的子矩阵的所...~

始发于微信公众号: 程序员小乐

专注于编程、互联网动态。最终将总结的技术、心得、经验(数据结构与算法、源码分析等)分享给大家,这里不只限于技术!还有职场心得、生活感悟、以及面经点击上方 “程序员小乐” ,选择“置顶公众号”,第一时间送达!


每日英文
Whatever you are facing today, remember to give yourself some credit for making it this far. You are stronger than you know.
无论你今天要面对什么,既然走到了这一步,就奋 斗下去,给自己一些肯定,你比自己想象中要坚强。

乐乐有话说
人生须有四得,既沉得住气,变得了脸,弯得下腰,抬得起头。人生须有四种经历,耐得住寂寞,经得起考验,承受了压力,面对了孤独。

面试算法代码知识梳理系列




一、概要

本文介绍了有关数组的算法第二部分的Java代码实现,所有代码均可通过 在线编译器(https://tool.lu/coderunner/) 直接运行,算法目录:

  • 找到最小的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<lLen; i++) {
           l[i] = p[startIndex+i];
       }
       l[i] = 1 << 30;
       for (i=0; i<rLen; i++) {
           r[i] = p[startIndex+lLen+i];
       }
       r[i] = 1 << 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

如何您想进技术群交流,关注公众号在后台回复 “加群”,或者 “学习” 即可

来自:泽毛

链接:https://www.jianshu.com/p/2addad265948

著作权归作者所有,欢迎投稿。

面试算法知识梳理五:数组第二部分


推荐阅读






看完本文有收获?请转发分享给更多人
关注「程序员小乐」,提升技能

以上就是:面试算法知识梳理五:数组第二部分 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论