274-H指数

[gitmikayao]

题目： 给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。

h 指数的定义： h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 N - h 篇论文每篇被引用次数 不超过 h 次。

例如： 某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。

示例：

输入：citations = [3,0,6,1,5]

输出：3

解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。

由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

提示： 如果 h 有多种可能的值，h 指数是其中最大的那个。

来源：H指数

思路分析：

• 根据h指数的定义可知：本题中的h指数肯定是<=数组的长度n的，

• 所有引用次数大于n的都可以设为n，不会影响h指数的结果，

• 这里的引用次数0可以不考虑，不会影响h的值，

• 遍历数组，如果nums[i]-1对应位置的元素如果不小于0，则对应取负数 nums[nums[i]-1] = -1，如果小于0，说明是第二次出现，在原来基础上减1nums[nums[i]-1]-=1，

• 同时，设置nums[i]的值，

• • 如果nums[nums[i]-1]的值大于0，分两种情况：如果大于零并且不等于i+1，则nums[i] = nums[nums[i]-1],进入到下一轮的处理；否则nums[i]=-1;
  • 如果nums[nums[i]-1]的值不大于0，nums[nums[i]-1]=0;

• 现在的数组中存储的就是每种引用次数出现的次数的负值，所以从尾部遍历数组，并累加次数，当次数大于等于下标i+1的时候，就是所求值。

代码：

export const hIndex = (nums: Array<number>) => {
  const len = nums.length;
  let h = 0;
  for (let i = 0; i < len; i++) {
    while (nums[i] > 0) {
      if (nums[i] > len) {
        nums[i] = len;
      }

      const temp = nums[nums[i] - 1];
      if (temp >= 0) {
        nums[nums[i] - 1] = -1;
      } else if (temp < 0) {
        nums[nums[i] - 1] -= 1;
      }

      if (temp > 0) {
        if (temp === i + 1) {
          nums[i] = -1;
        } else {
          nums[i] = temp;
        }
      } else {
        nums[i] = 0;
      }
    }
  }

  let count = 0;
  for (let i = len - 1; i >= 0; i--) {
    count += Math.abs(nums[i]);
    if (count >= i + 1) {
      return i + 1;
    }
  }

  return h;
}

复杂度分析：

• 时间复杂度：O(n),遍历数组，这里的while对每个元素不会重复。

• 空间复杂度：O(1)，在原来的数组上完成操作，使用部分临时变量。