274. H-Index
Tags:
Medium
Skills:
Array
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm chỉ số h-index của một nhà nghiên cứu, tức là giá trị lớn nhất của h sao cho có ít nhất h bài báo với mỗi bài có ít nhất h trích dẫn
💡
Cách tính H-index
- Liệt kê tất cả các bài báo của nhà khoa học, kèm số lần trích dẫn của từng bài\
- Sắp xếp danh sách này theo số lần trích dẫn giảm dần (từ cao nhất xuống thấp nhất)
- Duyệt từ bài đầu tiên, xác định vị trí lớn nhất h sao cho bài báo thứ h có ít nhất h trích dẫn
- H-index chính là giá trị h này
Approach
- Sắp xếp mảng citations giảm dần
- Duyệt từ đầu mảng , với mỗi vị trí
inếucitations[i] >= i + 1thì cập nhậth = i + 1 - Khi gặp
citations[i] < i + 1thì dừng lại và return lạih
Time and space complexity
- TC: O(nlogn)
- SC: O(1)
Solution
typescripttypescript
1function hIndex(citations: number[]): number {
2 citations.sort((a, b) => b - a)
3 let h = 0;
4 for (let i = 0; i < citations.length; i++) {
5 if (citations[i] >= i + 1) {
6 h = i + 1
7 } else {
8 break
9 }
10 }
11 return h
12};Approach - Counting Sort
- Dùng mảng đếm (counting sort) để đếm số lượng bài báo có số trích dẫn nhất định
- Đếm ngược từ số lượng bài báo lớn nhất, cộng dồn số bài có số trích dẫn lớn hơn ≥ h cho đến khi tổng số bài ≥ h thì return h
Time and space complexity
- TC: O(n)
- SC: O(n)
Solution
typescripttypescript
1function hIndex(citations: number[]): number {
2 const n = citations.length;
3 const count = new Array(n + 1).fill(0);
4 for(const c of citations) {
5 count[Math.min(c, n)]++
6 }
7 let s =0;
8 for(let h = n; h >= 0; h--) {
9 s+=count[h];
10 if(s>=h) return h
11 }
12
13 return 0
14};💡
Tại sao lại có condition s≥h return h
- h: Là số trích dẫn giả định (từ lớn nhất đến nhỏ nhất)
- s: Là tổng số bài báo có số trích dẫn ≥ h
H-index là số nguyên lớn nhất h sao cho có ít nhất h bài báo, mỗi bài được trích dẫn ít nhất h lần.
- Khi bạn duyệt từ h = n về 0:
- Ở mỗi giá trị h, bạn cộng dồn số bài báo có số trích dẫn ≥ h vào biến s.
- Nếu tại một thời điểm nào đó, s ≥ h, nghĩa là đã có ít nhất h bài báo được trích dẫn ít nhất h lần.
- Đây chính là điều kiện xác định H-index!
💡
Tại sao lại cần build Array(n + 1)
- Mỗi chỉ số trong mảng
countđại diện cho số lượng bài báo có số trích dẫn nhất định. - Với chỉ số từ
0đếnn-1, bạn lưu số bài báo có đúng 0, 1, ..., n-1 trích dẫn. - Với chỉ số
n, bạn gom tất cả các bài báo có số trích dẫn lớn hơn hoặc bằngnvào đây. - Lý do: H-index không bao giờ lớn hơn tổng số bài báo (nên nếu một bài báo có 100 hay 1000 trích dẫn thì cũng chỉ ảnh hưởng đến H-index tối đa là
n). - Vì vậy, mọi giá trị lớn hơn
nđều được tính chung vàocount[n].