275.c

#include<stdio.h>
#include<assert.h>

staticinlineintmin(inta, intb) {
return (a<b) ? a : b;
}

/* from current position to the end, we can caculate an hIndex array
 the hIndex will first ascend and then descend
 so the problem is to find the peak of the hIndex array
 we use binary search */

inthIndex(int*citations, intcitationsSize) {
if (citations==NULL||citationsSize==0) return0;

if (citationsSize==1) returnmin(citations[0], 1);

inti=0, j=citationsSize-1;
inth_prev, h_middle, h_next;

while (i <= j) {
intm=i+ (j-i) / 2;
h_prev=min(citations[m-1], citationsSize-m+1);
h_middle=min(citations[m], citationsSize-m);
h_next=min(citations[m+1], citationsSize-m-1);
if (h_prev <= h_middle&&h_middle>h_next) {
break;
 }
elseif (h_middle <= h_next) {
i=m+1;
 }
elseif (h_middle>h_next) {
j=m-1;
 }
else {
i++;
 }
 }

returnh_middle;
}

inthIndex0(int*citations, intcitationsSize) {
if (citations==NULL||citationsSize==0) return0;

inti=0, j=citationsSize-1;
while (i <= j) {
intm=i+ (j-i) / 2;
if (citations[m] >= citationsSize-m) {
j=m-1;
 }
else {
i=m+1;
 }
 }

returncitationsSize-i;
}

intmain() {

intcitations0[] = { 0, 1, 3, 5, 6 };
intcitations1[] = { 0, 3, 3, 3, 4 };
intcitations2[] = { 0, 3, 4, 4, 4, 4, 5, 5 };

assert(hIndex(citations0, sizeof(citations0) / sizeof(citations0[0])) ==3);
assert(hIndex(citations1, sizeof(citations1) / sizeof(citations1[0])) ==3);
assert(hIndex(citations2, sizeof(citations2) / sizeof(citations2[0])) ==4);

printf("all tests passed!\n");

return0;
}