Majority element done!

Easy, after Java version. Note that don't use ++i or i++, use i = i + 1
instead.

2 files changed, 80 insertions, 0 deletions

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)
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/majority_elementTest.py b/AlgoDesignAndTechniqueEdxPython/tests/majority_elementTest.py
new file mode 100644
index 0000000..b886710
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/majority_elementTest.py
@@ -0,0 +1,44 @@
+'''
+Created on Oct 31, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.majority_element import getMajorityElement
+
+class Test(unittest.TestCase):
+
+
+    def testGetMajorityElement1(self):
+        a = [1,1]
+        self.assertEqual(1, getMajorityElement(a, 0, len(a)-1))
+
+    def testGetMajorityElement2(self):
+        a = [1,2]
+        self.assertEqual(-1, getMajorityElement(a, 0, len(a)-1))
+
+    def testGetMajorityElement3(self):
+        a = [1,2,1]
+        self.assertEqual(1, getMajorityElement(a, 0, len(a)-1))
+
+    def testGetMajorityElement4(self):
+        a = [1,2,2]
+        self.assertEqual(2, getMajorityElement(a, 0, len(a)-1))
+
+    def testGetMajorityElement5(self):
+        a = [1]
+        self.assertEqual(1, getMajorityElement(a, 0, len(a)-1))
+
+    def testGetMajorityElement6(self):
+        a = [1, 2, 2, 2]
+        self.assertEqual(2, getMajorityElement(a, 0, len(a)-1))
+
+    def testGetMajorityElement7(self):
+        a = [2, 3, 9, 2, 2]
+        self.assertEqual(2, getMajorityElement(a, 0, len(a)-1))
+
+
+if __name__ == "__main__":
+    #import sys;sys.argv = ['', 'Test.testName']
+    unittest.main()
\ No newline at end of file