This article is participating in Python Theme Month. See the link for details

## Topic describes

This is 275. H index II on LeetCode, with medium difficulty.

Tag: “Dichotomy”

Given an array of citations for a researcher’s paper (citations are a non-negative integer), the array has been sorted in ascending order. Write a method to calculate the researcher’s H-index.

Definition of the H-index: “H stands for high citations. A researcher’s H-index means that h of his or her papers have been cited at least H times. (The other N-H papers were cited no more than H times each.) “

Example:

`Input: citations = [0,1,3,5,6] Output: 3 Explanation: The given array means that the researcher has a total of 5 papers, and each paper has been cited 0,1,3,5,6 times accordingly. Since three of the researchers' papers were cited at least three times each, and the other two papers were cited no more than three times each, her H-index was 3.Copy the code`

Description:

If there are many possible values for h, h to the power is the largest of them.

Advanced:

- This is an extension of the H exponent. In this case, the array of citations is guaranteed to be ordered.
- Can you optimize your algorithm to log time complexity?

## Fundamental analysis

There are two main differences between this case and the 274.H index:

- The range of NNN in 274. H index is 500050005000. In this case, the range of NNN is 10510^5105.
- Whether the given array is ordered: The array is not necessarily ordered in the 274. H index, in this case it is.

Obviously, the addition of the array ordering feature extends the range of data. You can guess that there are less time – complex algorithm implementations that take advantage of this feature.

## Dichotomous answer (linear`check`

)

In 274. H index, we use O(nlogn)O(n\log{n})O(nlogn) dichotomy, the main bottleneck of the algorithm is O(n)O(n)O(n) O(n) complexity check.

Of course, for 10510^5105, there is no problem using O(nlogn)O(n\log{n})O(nlogn) complexity.

Java code:

```
class Solution {
public int hIndex(int[] cs) {
int n = cs.length;
int l = 0, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(cs, mid)) l = mid;
else r = mid - 1;
}
return r;
}
boolean check(int[] cs, int mid) {
int ans = 0;
for (int i : cs) if (i >= mid) ans++;
returnans >= mid; }}Copy the code
```

Python 3 code:

```
class Solution:
def hIndex(self, citations: List[int]) - >int:
def check(cs, mid) :
return sum(i>=mid for i in cs) >= mid
n = len(citations)
l, r = 0, n
while l < r:
mid = l + r + 1 >> 1
if check(citations, mid):
l = mid
else:
r = mid - 1
return r
Copy the code
```

- Time complexity: Yes$[0, n]$Let’s do the dichotomy, and the complexity is zero$O(\log{n})$;
`check`

The function requires linear traversal of the array with the complexity of$O(n)$. The overall complexity is$O(n\log{n})$ - Space complexity: O(1)O(1)O(1)

## Binary subscript (based on and$citations[i]$Relationship)

In solution one, it is clear that we are not taking advantage of the “array ordering” property of this case.

According to the definition, H index if citationscitationscitations ascending, in one of the biggest eligible point on the right side of the XXX (include dividing point), Citations [I]>=xcitations[I]>=xcitations[I]>=xcitations[I]>=x, we should count them, for the left side of the partition point, Citations [I]>= xCitations [I]>= xCitations [I]>= X.

Therefore, we can use the number of books to the right of the partition point and the size of citations[x]citations[x] for dichotomy.

It is assumed that there are real segmentation points subscript XXX, whose value is citations[x] Citations [x]citations[X], and the number of values to the right of the segmentation points is N − Xn-xn − X. According to the definition of H index, Citations [x]>=n− xCitations [x]>= n-xCitations [x]>= N −x

- To the right of the partition point XXX: Citations [I]citations[I] non-strictly monotonically increasing, while the number of books strictly monotonically decreasing, Still satisfies the citations[I]>= N − ICitations [I]>=n− I relationship;
- To the left of the partition point XXX: Citations [I] Citations [I] non-strictly monotonically decreasing, the number of books strictly monotonically increasing, XXX as the real segmentation point, The citations[I]>= N − ICitations [I]>= n-ICitations [I]>= N − I relationship must therefore not be satisfied.

Use this “duality” for dichotomy, dichotomy subscript, and then calculate the number of books.

Java code:

```
class Solution {
public int hIndex(int[] cs) {
int n = cs.length;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (cs[mid] >= n - mid) r = mid;
else l = mid + 1;
}
return cs[r] >= n - r ? n - r : 0; }}Copy the code
```

Python 3 code:

```
class Solution:
def hIndex(self, citations: List[int]) - >int:
n = len(citations)
l, r = 0, n - 1
while l < r:
mid = l + r >> 1
if citations[mid] >= n - mid:
r = mid
else:
l = mid + 1
return n - r if citations[r] >= n - r else 0
Copy the code
```

- Time complexity: O(logn)O(\log{n})O(logn)
- Space complexity: O(1)O(1)O(1)

## Other “dichotomy” related content

The title | Answer key | The difficulty | Recommend index |
---|---|---|---|

4. Find the median of two positive ordinal groups | LeetCode problem solving link | difficult | 🤩 🤩 🤩 🤩 |

29. Divide two numbers | LeetCode problem solving link | medium | 🤩 🤩 🤩 |

33. Search rotation sort array | LeetCode problem solving link | medium | 🤩 🤩 🤩 🤩 🤩 |

34. Find the first and last positions of elements in a sorted array | LeetCode problem solving link | medium | 🤩 🤩 🤩 🤩 🤩 |

35. Search for insertion locations | LeetCode problem solving link | simple | 🤩 🤩 🤩 🤩 🤩 |

74. Search a two-dimensional matrix | LeetCode problem solving link | medium | 🤩 🤩 🤩 🤩 |

81. Search rotated sorted array II | LeetCode problem solving link | medium | 🤩 🤩 🤩 🤩 |

Find the minimum value in the rotation sort array | LeetCode problem solving link | medium | 🤩 🤩 🤩 |

Find the minimum value II in the rotation sorted array | LeetCode problem solving link | difficult | 🤩 🤩 🤩 |

220. Presence of repeated element III | LeetCode problem solving link | medium | 🤩 🤩 🤩 |

274. H index | LeetCode problem solving link | medium | 🤩 🤩 🤩 |

278. The first incorrect version | LeetCode problem solving link | simple | 🤩 🤩 🤩 🤩 |

354. Russian nesting envelope problem | LeetCode problem solving link | difficult | 🤩 🤩 🤩 |

363. The rectangular region does not exceed the maximum numerical sum of K | LeetCode problem solving link | difficult | 🤩 🤩 🤩 |

374. Guess the number size | LeetCode problem solving link | simple | 🤩 🤩 🤩 |

778. Swimming in a pool with a rising water level | LeetCode problem solving link | difficult | 🤩 🤩 🤩 |

852. Peak index of the mountain array | LeetCode problem solving link | simple | 🤩 🤩 🤩 🤩 🤩 |

981. Time-based key-value storage | LeetCode problem solving link | medium | 🤩 🤩 🤩 🤩 |

1004. Maximum number of consecutive 1s III | LeetCode problem solving link | medium | 🤩 🤩 🤩 |

Ability to deliver packages within D days | LeetCode problem solving link | medium | 🤩 🤩 🤩 🤩 |

1208. Make strings as equal as possible | LeetCode problem solving link | medium | 🤩 🤩 🤩 |

1438. The longest continuous subarray whose absolute difference does not exceed the limit | LeetCode problem solving link | medium | 🤩 🤩 🤩 |

1482. Minimum number of days required to make m bouquets | LeetCode problem solving link | medium | 🤩 🤩 🤩 |

1707. The maximum xor value of an element in the array | LeetCode problem solving link | difficult | 🤩 🤩 🤩 |

1751. Maximum number of meetings that can be attended II | LeetCode problem solving link | difficult | 🤩 🤩 🤩 |

## The last

This is the No.275 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode by the start date, some of which have locks, we will first finish all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.