目录1.H 指数 II2.窥视迭代器3.二维区域和检索 - 矩阵不可变1.H 指数 II给你一个整数数组 citations 其中 citations[i] 表示研究者的第 i 篇论文被引用的次数citations 已经按照 非降序排列 。计算并返回该研究者的 h 指数。h 指数的定义h 代表“高引用次数”high citations一名科研人员的 h 指数是指他她的 n 篇论文中至少 有 h 篇论文分别被引用了至少 h 次。请你设计并实现对数时间复杂度的算法解决此问题。示例 1输入citations [0,1,3,5,6]输出3解释给定数组表示研究者总共有 5 篇论文每篇论文相应的被引用了 0, 1, 3, 5, 6 次。由于研究者有3篇论文每篇 至少 被引用了 3 次其余两篇论文每篇被引用 不多于 3 次所以她的 h 指数是 3 。示例 2输入citations [1,2,100]输出2思路贪心加二分一共有n篇文章文章引用按升序排序可以以下标作为引用次数计数[1,2,3,4,…,n]在citations[k]处判断是否有n-k篇文章计数超过n-k若有则h≥n-k右半部分忽略继续搜索左半部分是否能大于n-k否则hn-k左半部分忽略搜索右半部分找到hclassSolution{publicinthIndex(int[]citations){intncitations.length;intl0,rn-1;inth0;//这里是lr还是lr取决于[l,r]是开区间还是闭区间//开区间用lr闭区间用lrwhile(lr){intmid(lr)/2;intcntn-mid;intctcitations[mid];if(cntct){hMath.max(h,ct);lmid1;}else{hMath.max(h,cnt);rmid-1;}}returnh;}}时间复杂度O ( l o g n ) O(logn)O(logn)空间复杂度O ( 1 ) O(1)O(1)2.窥视迭代器请你在设计一个迭代器在集成现有迭代器拥有的 hasNext 和 next 操作的基础上还额外支持 peek 操作。实现 PeekingIterator 类PeekingIterator(Iterator nums) 使用指定整数迭代器 nums 初始化迭代器。int next() 返回数组中的下一个元素并将指针移动到下个元素处。bool hasNext() 如果数组中存在下一个元素返回 true 否则返回 false 。int peek() 返回数组中的下一个元素但 不 移动指针。注意每种语言可能有不同的构造函数和迭代器 Iterator但均支持 int next() 和 boolean hasNext() 函数。示例 1输入[“PeekingIterator”, “next”, “peek”, “next”, “next”, “hasNext”][[[1, 2, 3]], [], [], [], [], []]输出[null, 1, 2, 2, 3, false]解释PeekingIterator peekingIterator new PeekingIterator([1, 2, 3]); // [1,2,3]peekingIterator.next(); // 返回 1 指针移动到下一个元素 [1,2,3]peekingIterator.peek(); // 返回 2 指针未发生移动 [1,2,3]peekingIterator.next(); // 返回 2 指针移动到下一个元素 [1,2,3]peekingIterator.next(); // 返回 3 指针移动到下一个元素 [1,2,3]peekingIterator.hasNext(); // 返回 False思路用一个变量保存下一个数字这样每次peek时只用输出变量即可指针不会移动。而每次调用next时输出变量再将变量指向真正的下一个数字。调用hasNext时判断变量是否为空为空则无下一个数字。classPeekingIteratorimplementsIteratorInteger{privateIteratorIntegerit;privateIntegernextElement;publicPeekingIterator(IteratorIntegeriterator){// initialize any member here.ititerator;nextElementit.next();}// Returns the next element in the iteration without advancing the iterator.publicIntegerpeek(){returnnextElement;}// hasNext() and next() should behave the same as in the Iterator interface.// Override them if needed.OverridepublicIntegernext(){IntegerresnextElement;nextElementit.hasNext()?it.next():null;returnres;}OverridepublicbooleanhasNext(){returnnextElement!null;}}3.二维区域和检索 - 矩阵不可变给定一个二维矩阵 matrix以下类型的多个请求计算其子矩形范围内元素的总和该子矩阵的 左上角 为 (row1, col1) 右下角 为 (row2, col2) 。实现 NumMatrix 类NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。示例 1输入:[“NumMatrix”,“sumRegion”,“sumRegion”,“sumRegion”][[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]输出:[null, 8, 11, 12]解释:NumMatrix numMatrix new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)思路二维数组保存前缀和classNumMatrix{privateint[][]sumMatrix;publicNumMatrix(int[][]matrix){intnmatrix.length,mmatrix[0].length;sumMatrixnewint[n][m];for(inti0;in;i){intsum0;for(intj0;jm;j){summatrix[i][j];if(i0){sumMatrix[i][j]sum;}else{sumMatrix[i][j]sumMatrix[i-1][j]sum;}}}}publicintsumRegion(introw1,intcol1,introw2,intcol2){// return sumMatrix[row2][col2]sumMatrix[row1-1][col1-1]-sumMatrix[row2][col1-1]-sumMatrix[row1-1][col2];intlRegioncol10?0:sumMatrix[row2][col1-1];intuRegionrow10?0:sumMatrix[row1-1][col2];intunRegioncol10||row10?0:sumMatrix[row1-1][col1-1];returnsumMatrix[row2][col2]-lRegion-uRegionunRegion;}}时间复杂度O ( 1 ) O(1)O(1)每一次求和时间复杂度为常数空间复杂度O ( n ∗ m ) O(n*m)O(n∗m)