Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?
[分析]
思路:二分查找。参考解法
https://leetcode.com/discuss/56122/standard-binary-search
自己的实现倒也是二分查找,但因为没有理解二分查找的精髓,写得磕磕碰碰,修修补补才被Accept,代码因此也不好看,yb君一开始甚至以为是错误的。看讨论区高票解法时觉得不理解,为什么不用考虑我实现中需要的特殊情形呢,为什么return 那样写。yb君指点说,使用二分查找解题时要清楚左右边界代表的含义,参考解法中[left, right]表示尚待判断的区间,[0, left -1]表示已确认不属于目标集合的区间,而[right+1, N - 1]表示已确认属于目标集合的区间。
换句话说right表示不属于目标集合的最大下标。因此迭代结束,right + 1是目标集合的第一个元素。目标集合中元素的性质是citations[i] >= 目标集合大小。
public class Solution {
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0)
return 0;
int N = citations.length;
int left = 0, right = N - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (citations[mid] == N - mid)
return citations[mid];
else if (citations[mid] > N - mid)
right = mid - 1;
else
left = mid + 1;
}
return N - (right + 1);
}
}
分享到:
相关推荐
leetcode题库 LeetCode-PHP 坚持每天做算法题 (๑╹ヮ╹๑)ノ Studying makes me happy 文件夹 Array 数组 Backtracking 回溯算法 Binary Search 二分查找 Bit Manipulation 位运算 Breadth ...h ...index.ph
博弈问题 leetcode Design-7 Problem1 LFU Cache () Problem2 H-Index () Problem2 Snake game ()
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary ...II ...#274 H-Index #283 Move Zeroes #292 Nim Game #318 Maximum P
H-Index II 二分查找 最短词距 最短词距 II 最短词距 III 包含重复 包含重复 II 包含重复 III 跳跃游戏 跳跃游戏二 买卖股票的最佳时机 买卖股票的最佳时机 II 买卖股票的最佳时机 III 买卖股票的最佳时机 IV 有冷却...
137 | [Single Number II](https://leetcode.com/problems/single-number-ii/) | [C++](./C++/single-number-ii.cpp) [Python](./Python/single-number-ii.py) | _O(n)_ | _O(1)_ | Medium ||| 190 | [Reverse Bits]...
二、Index目录引导 其中数字表示题目的顺序编号 1.运算基础(数字的基本运算、简单的求和等) 01 Two Sum :两数之和 07 Reverse Integer:翻转整数 09 Palindrome Number:回文数 11 Container With Most Water:双...
leetcode 答案 Conquer-Leetcode Binary Search 二分法 前提:有序!!! 【Arrays.sort(nums)--...H-Index II 注意是找后面的target 而且是动态target sqrtx 答案集进行二分 找 mid <= x/mid 的最后一个值 Find Pea
E:简单,M:中等,H:困难 数组和字符串 217. Contains Duplicate (E) 48. Rotate Image (M) -> 2 73. Set Matrix Zeroes (M) 1. Two Sum (E) 167. Two Sum II - Input array is sorted (E) 653. Two Sum IV - ...
H-Index II(二分搜索) 第441章排列硬币(二元搜索) #107. 二叉树层次遍历二(BFS树) #79. 词搜索 (DFS) 第797章从源到目标的所有路径 (DFS) 树 #107. 二叉树层次遍历二(BFS树) #106. 从中序和后序遍历(递归)...
leetcode中国 买卖股票 从easy一直问到hard 数独 从medium的判断是不是valid 到 hard的solve 数独 从BST里面删除一个node (要求写test case) design就是皮毛的问题。。。我几乎就是把Harvard那个intro system design...
leetcode卡 Best Practice 通过让路由的父级渲染一个单独的 router-view 组件,来实现多级路由的嵌套关系 { path: '/survey', name: 'questionnaire', component: { render: h => ( ) }, children:[ //... ] } ...
H-Index 1 相同,但问题陈述建议使用二分搜索; 在讨论中还发现了一个有趣的想法,可以进一步改善运行时。 8月3日 难的 8月4日 中等的 8月4日 中等的 1 次错误提交 - 超出时间限制,需要进行简单但至关重要的优化。 ...
加油站 leetcode 力扣_实践 标签: leetcode ...275_H_Index_II 217_Contain_Duplicate 55_Jump_Game 45_Jump_Game_II 121_Best_Time_to_Buy_and_Sell_Stock 122_Best_Time_to_Buy_and_Sell_Stock_
H指数(H Index) 最近最少使用(Least Recently Used) 最近最少频率使用缓存(LFU Cache) 线性同余生成器(Linear Congruential Generator) 最近最久未使用缓存(LRU Cache) 魔幻菱形模式(Magic Diamond ...
H-Index II 暴力枚举法 Subsets Subsets II Permutations Permutations II Combinations Letter Combinations of a Phone Number 广度优先搜索 Word Ladder Word Ladder II Surrounded Regions 总结 深度优先搜索 ...
:backhand_index_pointing_right: 如果你不知道该学习什么的话,请看 (原创不易,欢迎点赞),这是 2021 最新最完善的 Java 学习路线! :backhand_index_pointing_right: Java学习资源汇总(个人总结) Java基础到...