Update h-index.py

kamyu104 · kamyu104 · commit ad47fb85e5c2 · 2015-09-04T09:29:16.000+08:00
diff --git a/Python/h-index.py b/Python/h-index.py
@@ -1,5 +1,5 @@
-# Time:  O(nlogn)
-# Space: O(1)
+# Time:  O(n)
+# Space: O(n)
 
 # 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.
@@ -19,6 +19,29 @@
 #
 
 class Solution(object):
+    def hIndex(self, citations):
+        """
+        :type citations: List[int]
+        :rtype: int
+        """
+        n = len(citations);
+        count = [0] * (n + 1)
+        for x in citations:
+            if x >= n:
+                count[n] += 1
+            else:
+                count[x] += 1
+
+        h = 0
+        for i in reversed(xrange(0, n + 1)):
+            h += count[i]
+            if h >= i:
+                return i
+        return h
+
+# Time:  O(nlogn)
+# Space: O(1)
+class Solution2(object):
     def hIndex(self, citations):
         """
         :type citations: List[int]
