http://en.wikipedia.org/wiki/H-index
这个维基页面是h-index的定义
基本上如果我有一个[0 3 4 7 8 9 10]的数组，我的h指数将是4，因为我有4个大于4的数字。如果我有5个，我的h指数将是5数字大于5，等等。给定一个大于或等于0的整数数组，有效计算h指数的方法是什么？
编辑：数组不一定排序
http://en.wikipedia.org/wiki/H-index
这个维基页面是h-index的定义
基本上如果我有一个[0 3 4 7 8 9 10]的数组，我的h指数将是4，因为我有4个大于4的数字。如果我有5个，我的h指数将是5数字大于5，等等。给定一个大于或等于0的整数数组，有效计算h指数的方法是什么？
编辑：数组不一定排序
我在这里实现 上） 有表格，这很简单，很快：
private static int GetHIndex(int[] m)
{
int[] s = new int[m.Length + 1];
for (int i = 0; i < m.Length; i++) s[Math.Min(m.Length, m[i])]++;
int sum = 0;
for (int i = s.Length - 1; i >= 0; i--)
{
sum += s[i];
if (sum >= i)
return i;
}
return 0;
}
我在这里实现 上） 有表格，这很简单，很快：
private static int GetHIndex(int[] m)
{
int[] s = new int[m.Length + 1];
for (int i = 0; i < m.Length; i++) s[Math.Min(m.Length, m[i])]++;
int sum = 0;
for (int i = s.Length - 1; i >= 0; i--)
{
sum += s[i];
if (sum >= i)
return i;
}
return 0;
}
这可以在O（n）时间内完成。
在这里我假设n是奇数。偶数n改变算法（假设中位数为n / 2，则用n / 2替换（n + 1）/ 2）。而且，在O（n）时间内找到实际中值是复杂的。改为使用好的支点（如快速排序）。
复杂度：n + n / 2 + n / 4 ... = O（n）
这是我能想到的一个解决方案。不确定它是否是最好的。
按升序对数组进行排序。复杂 n日志（n）的
迭代索引中的数组 0到n。复杂性 ñ
并且对于每次迭代，假设索引是 一世
if (arr[i] == (arr.length - (i+1))
return arr[i]
例如。，
arr =[ 0 3 4 7 8 9 10 ]
arr[2] = 4
i = 2
arr.length = 7
4 = (7- (2+1))
我对我以前的实现不满意，所以我用一个用Java编写的更快的解决方案取而代之。
public int hIndex(int[] citations) {
if(citations == null || citations.length == 0)
{
return 0;
}
Arrays.sort(citations);
int hIndex = 0;
for(int i=0;i<citations.length;i++)
{
int hNew;
if(citations[i]<citations.length-i)
{
hNew = citations[i];
if(hNew>hIndex)
{
hIndex = hNew;
}
}
else if(citations[i]>=citations.length-i)
{
hNew = citations.length-i;
if(hNew>hIndex)
{
hIndex = hNew;
}
break;
}
}
return hIndex;
}