LeetCode 274

H-Index

Given an array of citations (each citation is a non-negative integer)
of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia:
"A scientist has index h if h of his/her N papers have
at least h citations each, and the other N ? h papers have
no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5],
which means the researcher has 5 papers in total and each of them
had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each
and the remaining two with no more than 3 citations each,
his h-index is 3.

Note:

If there are several possible values for h,
the maximum one is taken as the h-index.

Hint:

An easy approach is to sort the array first.
What are the possible values of h-index?
A faster approach is to use extra space.

  1 /*************************************************************************
  2     > File Name: LeetCode274.c
  3     > Author: Juntaran
  4     > Mail: JuntaranMail@gmail.com
  5     > Created Time: Thu 19 May 2016 20:47:36 PM CST
  6  ************************************************************************/
  7 
  8 /*************************************************************************
  9     
 10     H-Index
 11     
 12     Given an array of citations (each citation is a non-negative integer) 
 13     of a researcher, write a function to compute the researcher's h-index.
 14 
 15     According to the definition of h-index on Wikipedia: 
 16     "A scientist has index h if h of his/her N papers have 
 17     at least h citations each, and the other N ? h papers have 
 18     no more than h citations each."
 19 
 20     For example, given citations = [3, 0, 6, 1, 5], 
 21     which means the researcher has 5 papers in total and each of them 
 22     had received 3, 0, 6, 1, 5 citations respectively. 
 23     Since the researcher has 3 papers with at least 3 citations each 
 24     and the remaining two with no more than 3 citations each, 
 25     his h-index is 3.
 26 
 27     Note: 
 28     
 29     If there are several possible values for h, 
 30     the maximum one is taken as the h-index.
 31 
 32     Hint:
 33 
 34     An easy approach is to sort the array first.
 35     What are the possible values of h-index?
 36     A faster approach is to use extra space.
 37 
 38  ************************************************************************/
 39 
 40 #include "stdio.h"
 41 
 42 void quick_sort( int* nums, int left, int right )
 43 {
 44     if( left < right )
 45     {
 46         int i = left;
 47         int j = right;
 48         int flag = nums[left];
 49         
 50         while( i < j )
 51         {
 52             while( i<j && nums[j]>=flag )    // 从右向左找第一个小于x的数  
 53             {
 54                 j--;
 55             }
 56             if( i < j )
 57             {
 58                 nums[i++] = nums[j];
 59             }
 60         
 61             while( i<j && nums[i]<flag )    // 从左向右找第一个大于等于x的数
 62             {
 63                 i++;
 64             }
 65             if( i < j )
 66             {
 67                 nums[j--] = nums[i];
 68             }
 69         }  
 70         nums[i] = flag;
 71         quick_sort( nums, left, i-1 );
 72         quick_sort( nums, i+1, right);
 73     }
 74 }
 75 
 76 void printfNums( int* nums, int numsSize )
 77 {
 78     int i;
 79     for( i=0; i<numsSize; i++ )
 80     {
 81         printf("%d ", nums[i]);
 82     }
 83     printf("
");
 84 }
 85 
 86 int hIndex(int* citations, int citationsSize) 
 87 {
 88 
 89     quick_sort( citations, 0, citationsSize-1 );
 90     
 91     int i;
 92     for( i=0; i<citationsSize; i++ )
 93     {
 94         if( (citationsSize-i) <= citations[i] )
 95         {
 96             return citationsSize-i;
 97         }
 98     }
 99     return 0;
100 }
101 
102 int main()
103 {
104     int citations[] = {9,8,7,6,5,4,3,2,1};
105     int citationsSize = 9;
106     int left = 0;
107     int right = 8;
108     
109     printfNums( citations, citationsSize );
110     quick_sort( citations, left, right );
111     printfNums( citations, citationsSize );
112     
113     int ret = hIndex( citations, citationsSize );
114     printf("%d
", ret);
115     
116     return 0;
117 }