- 浏览: 130687 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.
Note: If there are several possible values for h, the maximum one is taken as the h-index.
[分析]
扫描一遍citations,使用一个额外数组count[]计数每个引用数的文章数量,引用数大于N(文章总数)的视作N。然后从后往前扫描count[],同时累加已扫描部分记为sum,sum表示引用数>=i的文章总数,因为count[]是从后往前扫描,发现的第一个i即为所求的h-index。
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.
Note: If there are several possible values for h, the maximum one is taken as the h-index.
[分析]
扫描一遍citations,使用一个额外数组count[]计数每个引用数的文章数量,引用数大于N(文章总数)的视作N。然后从后往前扫描count[],同时累加已扫描部分记为sum,sum表示引用数>=i的文章总数,因为count[]是从后往前扫描,发现的第一个i即为所求的h-index。
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]; // count[i] means number of articles which citations >= i for (int i = 0; i < N; i++) { if (citations[i] > N) count[N] += 1; else count[citations[i]] += 1; } int sum = 0; for (int i = N; i >= 0; i--) { sum += count[i]; if (sum >= i) return i; } return 0; } }
发表评论
-
Leetcode - Add Binary
2015-08-21 09:28 434[分析] 从低位往高位逐位相加,就是这么一个简单的题却花了我一 ... -
Leetcode - Longest Consecutive Sequence
2015-08-20 21:20 454[分析] base version说几句: 数组题一定要考虑重 ... -
Leetcode - First Missing Positive
2015-08-20 07:45 607[分析] 将各个正数放入相应下标处,使之满足nums[nums ... -
Leetcode - Set Matrix Zeros
2015-08-19 20:55 515Given a m x n matrix, if an ele ... -
Leetcode - Rotate Image
2015-08-19 19:51 466[分析] 自己的思路:从外到内一圈圈顺时针旋转90度,坐标映射 ... -
Missing Ranges
2015-08-19 09:48 485[分析] 此题若不考虑极大值极小值相关的corner case ... -
Leetcode - 3Sum Smaller
2015-08-18 22:12 1448Given an array of n integers nu ... -
Leetcode - Spiral Matrix II
2015-08-18 19:49 464Given an integer n, generate a ... -
Leetcode - Spiral Matrix
2015-08-18 09:50 393Given a matrix of m x n element ... -
Leetcode - Contains Duplicate II
2015-08-18 07:57 528Given an array of integers and ... -
Leetcode - Shortest Word Distance II
2015-08-18 07:25 1315This is a follow up of Shortest ... -
Leetcode - Shortest Word Distance III
2015-08-17 22:05 1628This is a follow up of Shortest ... -
Leetcode - Shortest Word Distance
2015-08-17 22:01 884Given a list of words and two w ... -
Leetcode - Insert Interval
2015-08-14 10:12 588[分析] 这道题思路直接,但bug free需要费些心力。第一 ... -
Leetcode - Valid Sudoku
2015-07-30 21:57 450Determine if a Sudoku is valid, ... -
Leetcode -Rotate Array
2015-07-21 08:16 509Rotate an array of n elements t ... -
Leetcode - House Robber II
2015-05-20 22:34 731Note: This is an extension of ... -
Leetcode - Largest Rectangle in Histogram
2015-05-20 07:53 462Given n non-negative integers ... -
MockInterview-IPRangeData Find&Insert
2015-04-12 08:09 0[题目] Finding the IP address w ... -
Leetcode - MissingRange
2015-03-31 09:25 419Given a sorted integer array ...
相关推荐
leetcode题库 LeetCode-PHP 坚持每天做算法题 (๑╹ヮ╹๑)ノ Studying makes me happy 文件夹 Array 数组 Backtracking 回溯算法 Binary Search 二分查找 Bit Manipulation 位运算 Breadth ...h ...index.ph
博弈问题 leetcode Design-7 Problem1 LFU Cache () Problem2 H-Index () Problem2 Snake game ()
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree ...#274 H-Index #283 Move Zeroes #292 Nim Game #318 Maximum P
H-Index II 二分查找 最短词距 最短词距 II 最短词距 III 包含重复 包含重复 II 包含重复 III 跳跃游戏 跳跃游戏二 买卖股票的最佳时机 买卖股票的最佳时机 II 买卖股票的最佳时机 III 买卖股票的最佳时机 IV 有冷却...
二、Index目录引导 其中数字表示题目的顺序编号 1.运算基础(数字的基本运算、简单的求和等) 01 Two Sum :两数之和 07 Reverse Integer:翻转整数 09 Palindrome Number:回文数 11 Container With Most Water:双...
leetcode 答案 Conquer-Leetcode Binary Search 二分法 前提:有序!!! 【Arrays.sort(nums)--...H-Index II 注意是找后面的target 而且是动态target sqrtx 答案集进行二分 找 mid <= x/mid 的最后一个值 Find Pea
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
E:简单,M:中等,H:困难 数组和字符串 217. Contains Duplicate (E) 48. Rotate Image (M) -> 2 73. Set Matrix Zeroes (M) 1. Two Sum (E) 167. Two Sum II - Input array is sorted (E) 653. Two Sum IV - ...
H-Index II(二分搜索) 第441章排列硬币(二元搜索) #107. 二叉树层次遍历二(BFS树) #79. 词搜索 (DFS) 第797章从源到目标的所有路径 (DFS) 树 #107. 二叉树层次遍历二(BFS树) #106. 从中序和后序遍历(递归)...
leetcode中国 买卖股票 从easy一直问到hard 数独 从medium的判断是不是valid 到 hard的solve 数独 从BST里面删除一个node (要求写test case) design就是皮毛的问题。。。我几乎就是把Harvard那个intro system design...
leetcode卡 Best Practice 通过让路由的父级渲染一个单独的 router-view 组件,来实现多级路由的嵌套关系 { path: '/survey', name: 'questionnaire', component: { render: h => ( ) }, children:[ //... ] } ...
H-Index 1 相同,但问题陈述建议使用二分搜索; 在讨论中还发现了一个有趣的想法,可以进一步改善运行时。 8月3日 难的 8月4日 中等的 8月4日 中等的 1 次错误提交 - 超出时间限制,需要进行简单但至关重要的优化。 ...
加油站 leetcode 力扣_实践 标签: leetcode ...275_H_Index_II 217_Contain_Duplicate 55_Jump_Game 45_Jump_Game_II 121_Best_Time_to_Buy_and_Sell_Stock 122_Best_Time_to_Buy_and_Sell_Stock_
H指数(H Index) 最近最少使用(Least Recently Used) 最近最少频率使用缓存(LFU Cache) 线性同余生成器(Linear Congruential Generator) 最近最久未使用缓存(LRU Cache) 魔幻菱形模式(Magic Diamond ...
H-Index II 暴力枚举法 Subsets Subsets II Permutations Permutations II Combinations Letter Combinations of a Phone Number 广度优先搜索 Word Ladder Word Ladder II Surrounded Regions 总结 深度优先搜索 ...
:backhand_index_pointing_right: 如果你不知道该学习什么的话,请看 (原创不易,欢迎点赞),这是 2021 最新最完善的 Java 学习路线! :backhand_index_pointing_right: Java学习资源汇总(个人总结) Java基础到...