O(logN)-time O(1)-space Easy Solution with Detailed Explanations (C++/Java/Python)


  • 19

    The basic idea of this solution is to use binary search to find the minimum index such that

    citations[index] >= length(citations) - index
    

    After finding this index, the answer is length(citations) - index.

    This logic is very similar to the C++ function lower_bound or upper_bound.


    Complexities:

    • Time: O(log n)
    • Space: O(1)

    C++:

    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            int size = citations.size();
    
            int first = 0;
            int mid;
            int count = size;
            int step;
            
            while (count > 0) {
                step = count / 2;
                mid = first + step;
                if (citations[mid] < size - mid) {
                    first = mid + 1;
                    count -= (step + 1);
                }
                else {
                    count = step;
                }
            }
            
            return size - first;
        }
    };
    

    Java:

    public class Solution {
        public int hIndex(int[] citations) {
            int len = citations.length;
    
            int first = 0;
            int mid;
            int count = len;
            int step;
            
            while (count > 0) {
                step = count / 2;
                mid = first + step;
                if (citations[mid] < len - mid) {
                    first = mid + 1;
                    count -= (step + 1);
                }
                else {
                    count = step;
                }
            }
            
            return len - first;
        }
    }
    

    Python:

    class Solution(object):
        def hIndex(self, citations):
            """
            :type citations: List[int]
            :rtype: int
            """
            
            length = len(citations)
            
            first = 0
            count = length
            
            while count > 0:
                step = count / 2
                mid = first + step
                if citations[mid] < length - mid:
                    first = mid + 1
                    count -= (step + 1)
                else:
                    count = step
            
            return length - first
    

    @daviantan1890 @ruichang Thank you for your comments and discussions.

    I am very sure that two-branch binary search is more efficient than three branch binary search.
    and (low + high) is not good idea since it may rely on the overflow behavior.
    In fact, using count step first mid is the standard implement way of C++, so I do not think there are better ways to implement the binary search.


  • 2

    Hi, zhiqing_xiao. Your idea is really nice. Well, I cheat the problem using lower_bound based on your idea :-)

    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            int n = citations.size();
            for (int i = 0; i < n; i++)
                citations[i] -= (n - i); 
            auto lb = lower_bound(citations.begin(), citations.end(), 0);
            return n - (lb - citations.begin());
        }
    }; 

  • 0

    @jianchao.li.fighter Thank you for your comment. Please also notice that the for loop in your code is O(n).


  • 0

    Hi, zhiqing_xiao. Yeah, you're right. Well, in fact I just take a quick test of your idea :-)


  • 0
    R
    class Solution {
    public:
        int hIndex(vector<int>& c) {
            int n = c.size();
            int low = 0, high = n;
            while(low<=high){
                if(low == high){
                    return n-high;
                }
                int mid= (low+high)>>1;
                if(c[mid] >= n - mid) high=mid;
                else low = mid+1;
            }
        }
    };
    

    ans is [0, n] which is very important, as mid can be sure to be<n, so no out of range


  • 1
    D

    I think return immediately would be better than we wait until the end. Like the following code:

    Java:

    public class Solution {  
        public int hIndex(int[] citations) {  
            int n = citations.length;  
            int start = 0;  
            int end = n-1;  
            int middle;  
            while (start <= end){  
                middle = (end-start)/2 + start;  
                if (citations[middle] == n-middle) return citations[middle];  
                else if(citations[middle] < n-middle) start = middle + 1;  
                else end = middle - 1;  
            }  
            return n - end - 1;  
        }  
    }  
    

    Python

    class Solution(object):  
        def hIndex(self, citations):              
            n = len(citations)   
            start, end = 0, n-1  
            while start <= end:  
                middle = (start + end) / 2  
                if citations[middle] == n-middle: return citations[middle]  
                elif citations[middle] < n - middle: start = middle + 1  
                else: end = middle - 1  
            return n-end-1  
    

    C++

    class Solution {  
    public:  
        int hIndex(vector<int>& citations) {  
            int n = citations.size();  
            int start = 0;  
            int end = n - 1;  
            int middle = 0;  
            while(start <= end){  
                middle = (end-start)/2 + start;  
                if (citations[middle] == n-middle) return citations[middle];  
                else if(citations[middle] < n-middle) start = middle + 1;  
                else end = middle - 1;  
            }  
            return n-end-1;  
        }  
    };  

  • 1
    L

    Could you explain for me, why the result is "size - left", please ???


  • 0
    Y

    In reality no human can cause overflow even if you call low + high.
    Common professors have only about 30 h-index.


  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.