未分類

H-Index II

BinarySearch, Go, LeetCode

H-Index II

Follow up for H-Index:

What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Default:

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

解答思路:

建議可以先參考先前H-Index的解法，解說較為詳細，概念上完全一樣，先前題目的程式碼甚至不需要修改，而且還已經先將整個引用次數做排序了，所以剩下的做法就和之前一模一樣沒有什麼大問題。

程式碼解說:

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

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

完整程式碼:

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

總結:

建議可以先參考先前H-Index的解法，解說較為詳細，概念上完全一樣，甚至這次還已經先將整個引用次數做排序了，所以剩下的做法就和之前一模一樣沒有什麼大問題。

分享到