主元素

yingl · yingl · commit bba70188b34a · 2016-08-04T13:37:00.000+08:00
diff --git a/majority_number.py b/majority_number.py
@@ -0,0 +1,18 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    """
+    @param nums: A list of integers
+    @return: The majority number
+    """
+    def majorityNumber(self, nums):
+        # write your code here
+        # 借鉴majority_number_ii.py的算法，复杂度降低到O(n)。
+        ret, count = 0, 0
+        for i in xrange(len(nums)):
+            if count == 0:
+                ret = nums[i]
+                count = 1
+            else:
+                count = (count + 1) if ret == nums[i] else (count - 1)
+        return ret
