尋找算法來計算h指數快速

http://en.wikipedia.org/wiki/H-index 尋找算法來計算h指數快速

此wiki頁面是h指數的定義

基本上如果我是具有[0 3 4 7 8 9 10]的數組，我的h-index是4，因爲我有4個大於4的數字。如果我有5個大於5的數字，那麼我的h-index應該是5等等。給定一個大於或等於0的整數數組，有效計算h指數的方法有哪些？

編輯：陣列不一定排序

2013-11-22 cakester

這裏我實現O（N）與桌遊戲，這是簡單和超快：

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; 
}

來源

2013-11-22 09:38:56

好的解決方案！ +1 – ElKamina

這個算法是錯誤的，它應該是'if（sum == i）return i;'。但即使如此，它計算出有'我'的數字比**更大**或相等**（根據鏈接而不是提問者想知道什麼是正確的）。另外，如果在第二個for循環中沒有匹配（因此返回），算法返回0，這意味着有0個數字大於（或大於或等於）0，這對於一個（非空的）是矛盾的）數組只包含大於或等於0的數字（至少如果您使用關係'> ='檢查，就像現在所做的那樣）。 –

沒有評論？沒有解釋？算法可能很好，但不要強迫讀者盯着它，至少要分享核心思想。 – timgeb

這是我能想到的一種解決方案。不確定它是否最好。

按升序對數組進行排序。複雜度nlog（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))

來源

2013-11-22 08:03:09

無需排序（O（nlogn））。在O（log N）'中看到我的解決方案是O（n） – ElKamina

__Sort__？真？你一定是天才。 –

對不起。 :)這是一個錯字 –

這可以在O（n）的時間來完成。

查找數組的中值。
如果中位數>（n-1）/ 2，那麼數字在中位數之前。迭代地查找它
如果中位數爲<（n-1）/ 2，則數字出現在中值之後。迭代查找它。
如果中值==第（n-1）/ 2，則中值是該溶液

在這裏，我假定n是奇數。對於偶數n稍微改變算法（假設中位數爲n/2，用n/2代替（n + 1）/ 2）。另外，在O（n）時間中找到實際的中位數很複雜。使用一個好的支點（就像在快速排序中一樣）。

複雜度：N + N/2 + N/4 ... = O（N）

來源

2013-11-22 08:03:15 ElKamina

awsome = D，我猜測線性是最好的結果 – cakester

這是NLogN，因爲中位數的搜索應該在所有數組中完成。 –

答案不在數組內的情況如何？示例[0 0 0 9 9 9] –

-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; 
}

來源

2015-09-09 09:05:08

尋找算法來計算h指數快速

回答

相關問題