leetCode Question: H-Index II

H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Analysis:

This problem added another condition that the array is already sorted. And the time requirement is restricted to O(log n). Naturally, O(log n) reminds us to use binary search approach.

Like other binary search problems, every time we find the middle element in the array, search or return differently according to the value of middle element and our goal. This time when we meet the middle element c[mid] in the array c, the conditions:

• if c[mid] == sz - mid, we have found the largest h-index, no mattter we go to the left or right of the array, there is no larger result we could find.
• if c[mid] < sz - mid, we might find a larger h-index by looking at elements to the right, let’s keep searching the right part of the array.
• if c[mid] > sz - mid, we might find a larger h-index by looking at elements to the left, let’s keep searching the left part of the array.

Code(C++):

class Solution {

public:

void search(vector<int>& citations, int st, int ed, int& res, int sz){

if (st > ed){

return;

}else{

int mid = st + (ed-st)/2;

if (sz-mid == citations[mid]){

res = sz-mid;

}else if (sz-mid > citations[mid]){

res = max(res, citations[mid]);

search(citations, mid+1, ed, res,sz);

}else{

res = max(res, sz-mid);

search(citations, st, mid-1, res,sz);

}

}

}

int hIndex(vector<int>& citations) {

int res = 0;

int sz = citations.size();

search(citations, 0, sz-1, res, sz);

return res;

}

};

Code (Python):

class Solution(object):

def search(self, citations, st, ed, res,l):

if st > ed:

return

else:

mid = st + (ed-st)/2

if citations[mid] == l-mid:

res[0] = citations[mid]

elif citations[mid] > l-mid:

res[0] = max(res[0], l-mid)

self.search(citations, st, mid-1, res,l)

else:

res[0] = max(res[0], citations[mid])

self.search(citations, mid+1, ed, res,l)

def hIndex(self, citations):

"""

:type citations: List[int]

:rtype: int

"""

res = [0]

l = len(citations)

self.search(citations, 0, l-1, res,l)

return res[0]