程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode 274] H

[LeetCode 274] H

編輯:關於C++

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:

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

    solution:

    1. O(nlog(n)), sort array, use definition to find maximum index.

    2. use extra space, O(n). counting sort

     

    public class Solution {
        public int hIndex(int[] citations) {
            if(citations.length <=0) return 0;
            int res = 0;
            int len = citations.length;
            int[] countarray = new int[len+1];
            for(int i=0;i=len) {
                    countarray[len]++;
                }else {
                    countarray[citations[i]]++;
                }
            }
            if(countarray[len]>=len) return len;
            for(int i=len-1;i>=0;i--){
                countarray[i] = countarray[i] + countarray[i+1];
                if(countarray[i]>=i) return i;
            }
            return res;
        }
    }


     

     

     

     

     

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved