[LeetCode 274] 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.
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;
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
