From 5b80f883649949d289aed52720d738c486621809 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 31 Oct 2018 21:39:52 -0500
Subject: Majority element done!

Easy, after Java version. Note that don't use ++i or i++, use i = i + 1
instead.---
 .../sources/majority_element.py                    | 36 ++++++++++++++++++++++
 1 file changed, 36 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/majority_element.py

(limited to 'AlgoDesignAndTechniqueEdxPython/sources')

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/majority_element.py b/AlgoDesignAndTechniqueEdxPython/sources/majority_element.py
new file mode 100644
index 0000000..c82b7af
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/majority_element.py
@@ -0,0 +1,36 @@
+# Uses python3
+import sys
+
+
+def getMajorityElement(a, left, right):
+    if left == right:
+        return a[left]
+    middle = (int) ((right - left) / 2)
+    b = getMajorityElement(a, left, left + middle)
+    c = getMajorityElement(a, left + middle + 1, right)
+    d = conquer(a[left:right + 1], b, c)
+    return d
+
+
+def conquer(a, b, c):
+    countB = 0
+    countC = 0
+    for i in a:
+        if i == b:
+            countB = countB + 1
+        if i == c:
+            countC = countC + 1
+    if countB > (len(a) / 2):
+        return b;
+    if countC > (len(a) / 2):
+        return c
+    return -1
+
+
+if __name__ == '__main__':
+    input = sys.stdin.read()
+    n, *a = list(map(int, input.split()))
+    if getMajorityElement(a, 0, n - 1) != -1:
+        print(1)
+    else:
+        print(0)
-- 
cgit v1.2.3