H-Index & II

mochixuan 发布于2019-08-14 17:25 / 2760人阅读

H-Index

题目链接：https://leetcode.com/problems...

sort：

public class Solution {
    public int hIndex(int[] citations) {
        if(citations == null || citations.length == 0)  return 0;
        // sort
        Arrays.sort(citations);
        int n = citations.length;
        // find 1st i that citations[i] < i
        // [0, 1, 3, 5, 6]
        for(int i = 0; i < n; i++) {
            if(citations[i] >= n - i) return n - i;
        }
        return 0;
    }
}

calculate suffix sum:

public class Solution {
    public int hIndex(int[] citations) {
        if(citations == null || citations.length == 0)  return 0;
        int n = citations.length;
        int[] count = new int[n + 1];
        for(int i = 0; i < n; i++) {
            if(citations[i] > n) {
                count[n]++;
            }
            else {
                count[citations[i]]++;
            }
        }
        
        // calculate suffix sum
        int sum = 0;
        for(int i = n; i >= 0; i--) {
            sum += count[i];
            if(sum >= i) return i;
        }
        return 0;
    }
}

H-Index II

题目链接：https://leetcode.com/problems...

public class Solution {
    public int hIndex(int[] citations) {
        if(citations == null || citations.length == 0)  return 0;
        // binary search, find 1st c[i] >= n - i
        int n = citations.length;
        int l = 0, r = n - 1;
        while(l + 1 < r) {
            int mid = l + (r - l) / 2;
            int val = citations[mid];
            if(val == n - mid) return n - mid;
            else if(val < n - mid) l = mid;
            else r = mid;
        }
        
        if(citations[l] >= n - l) return n - l;
        if(citations[r] >= n - r) return n - r;
        return 0;
    }
}

私有云服务器托管 II quartus ii ii6 ii7

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66621.html

[Leetcode] H-Index H指数

摘要：排序法复杂度时间空间思路先将数组排序，我们就可以知道对于某个引用数，有多少文献的引用数大于这个数。代码排序得到当前的指数数组映射法复杂度时间空间思路也可以不对数组排序，我们额外使用一个大小为的数组。 H-Index I Given an array of citations (each citation is a non-negative integer) of a research...

xumenger 2019-08-14 12:35 评论0 收藏0
274. H-Index

摘要：题目解答满足这个的最大值不会超过数组的因为如果超过了，就不可能有这么多的数。所以就是把所有可能的个至少有个的记下来，然后找出最大的。因为是从后向前扫的，所以当前的就是满足条件的最大数。题目：Given an array of citations (each citation is a non-negative integer) of a researcher, write a fun...

xiaochao 2019-08-14 14:09 评论0 收藏0
490. The Maze &amp;&amp; 505. The Maze II

摘要：题目链接和上一题不一样的是这道题要求最短的路径，普通的遍历和都是可以做的，但是求最短路径的话还是用。这里相当于每个点有至多条相连，每条的就是到墙之前的长度。 490. The Maze 题目链接：https://leetcode.com/problems... 又是图的遍历问题，就是简单的遍历，所以dfs和bfs都可以做，复杂度也是一样的。这道题要求球不能停下来，即使碰到destina...

BoYang 2019-08-14 17:27 评论0 收藏0
[LeetCode] Path Sum (I &amp; II &amp; III)

摘要： 112. Path Sum Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node...

张金宝 2019-08-19 11:09 评论0 收藏0
[LintCode/LeetCode] Single Number I &amp; II [位运算]

摘要：整个过程相当于，直接在和里去掉既是又是的。所以最后返回的，一定是只出现过一次的，而出现两次的都在里，出现三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 评论0 收藏0