H index II
https://leetcode.com/problems/h-index-ii/
Solution I : Binary search
public class Solution { public int hIndex(int[] citations) { int start = 0; int end = citations.length-1; int len = citations.length; int result = 0; int mid; while(start <= end){ mid = start + (end-start)/2; if(citations[mid] >= (len - mid)){ result = (len-mid); // nice trick if cant find the exact equal condition end = mid-1; } else{ start = mid + 1; } } return result; } }
Solution II: Standard binary search
Mind the equal condition
public class Solution { public int hIndex(int[] citations) { if(citations == null || citations.length == 0) return 0; int l = 0, r = citations.length; int n = citations.length; while(l < r){ int mid = l + (r - l) / 2; if(citations[mid] == n - mid) return n - mid; if(citations[mid] < citations.length - mid) l = mid + 1; else r = mid; } return n - l; } }
public int hIndex(int[] citations) { int l = 0, r = citations.length - 1; for (int m = (l + r) / 2; l <= r; m = (l + r) / 2) if (citations[m] < citations.length - m) l = m + 1; else r = m - 1; return citations.length - l; }
Check out more methods: