未分類

H-Index

Go, HashTable, LeetCode, Sort

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.

提示 解題應用
Sort 規律觀查

Default:

1
2
3
func hIndex(citations []int) int {
}

解答思路:

首先要先知道H-Index的定義是什麼，找維基百科來描述的話:

H-Index為：一個人在其所有學術文章中有N篇論文分別被引用了至少N次，他的H指數就是N。如美國耶魯大學免疫學家理察·弗來沃發表的900篇文章中，有107篇被引用了107次以上，他的H指數是107。

應該不難發現要找出H-Index就要有對應的文章數量與數量相符的引用次數，現在有一陣列紀錄著每篇文章引用的次數，要找出大部分文章最少都有某篇文章的引用次數，並統計符合條件的文章數來得出結果，那麼一開始就先將整個陣列做排序，如此一來每當取出一篇文章就可以確保後頭其它文章的引用次數最少都有與該文相等或更多，再來就只要確認該文的引用次數是否比後頭所有的文章數量相等或更多，如果是的話其後頭文章數量(包含取出的該篇文章)就會是H-Index，而如果後頭的文章數量比該文的引用次數要大的多，就再取下一遍文章找出更大引用次數(意思等同於找出更大的H-Index)，最後直到全數都取出完畢如果還是沒有找到H-Index就表示所有文章的引用次數全為0(寫一堆廢文的意思)。

程式碼解說:

如思路所述一開始就先將整個陣列做排序，接著就可以開始一一取出文章的引用次數，如果該文的引用次數比後頭所有的文章數量相等或更多，其後頭文章數量(包含取出的該篇文章)就會是H-Index(數量:文章總數-該文的index)，而如果後頭的文章數量比該文的引用次數要大的多，就再取下一遍文章找出更大引用次數(意思等同於找出更大的H-Index)，最後直到全數都取出完畢如果還是沒有找到H-Index就表示所有文章的引用次數全為0便向上回傳0。

1
2
3
4
5
6
7
sort.Ints(citations)
for i, v := range citations {
	if v >= len(citations)-i {
		return len(citations) - i
	}
}
return 0

完整程式碼:

1
2
3
4
5
6
7
8
9
func hIndex(citations []int) int {
	sort.Ints(citations)
	for i, v := range citations {
		if v >= len(citations)-i {
			return len(citations) - i
		}
	}
	return 0
}

總結:

現在有一陣列紀錄著每篇文章引用的次數，要找出H-Index就要有對應的文章數量與數量相符的引用次數，那麼一開始就先將整個陣列做排序，如此一來每當取出一篇文章就可以確保後頭其它文章的引用次數最少都有與該文相等或更多，再來就只要確認該文的引用次數是否比後頭所有的文章數量相等或更多，如果是的話其後頭文章數量(包含取出的該篇文章)就會是H-Index，而如果後頭的文章數量比該文的引用次數要大的多，就再取下一遍文章找出更大引用次數(意思等同於找出更大的H-Index)，最後直到全數都取出完畢如果還是沒有找到H-Index就表示所有文章的引用次數全為0。

分享到