H 指数

#leetcode #2024/08/19 #算法

目录

• 题目及理解
• 思路
  • 代码实现
  • 复杂度分析
  • 错误记录
• 其他思路

题目及理解

思路

• 将引用次数降序排序
• 从前向后遍历，当引用次数大于当前索引时，h 指数加 1

代码实现

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function (citations) {
  let res = 0;
  // ① 先排序，降序排序
  citations.sort((a, b) => b - a);

  // ②  从前向后遍历，当**引用次数大于当前索引**时，h 指数加 1 
  for (let i = 0; i < citations.length; i++) {
    //  如果当前引用数大于等于当前下标值，则 h 值为当前下标值
    if (citations[i] >= i + 1) {
      res = i + 1;
      // 否则，直接跳出循环
    } else {
      break;
    }
  }

  return res;
};

复杂度分析

• 时间复杂度分析：
  1. 排序步骤：
     • 使用了 JavaScript 的内置排序方法 sort()。
     • 大多数现代浏览器的 sort() 方法实现为快速排序的变体，平均时间复杂度为 O(n log n)。
  2. 遍历步骤：
     • 最坏情况下，需要遍历整个数组，复杂度为 O(n)。
  3. 总体时间复杂度：
     • O(n log n) + O(n) = O(n log n)
     • 排序步骤决定了整体的时间复杂度。
• 空间复杂度分析：
  1. 排序：
     • 取决于具体的排序算法实现。
     • 最好情况下是 O(1)，但某些实现可能需要 O(log n) 或 O(n) 的额外空间。
  2. 其他变量：
     • 使用了常数级额外空间（res 和 i）。
  3. 总体空间复杂度：
     • 主要取决于排序算法的实现，一般为 O(1) 到 O(n) 之间。

错误记录

其他思路

• 计数排序
• 二分查找法

[!danger] 但忽略了，第一种很直接了，别忘了目的何在，又不是做研究，没必要深究了