From 81692fe3e2b51ba1dfffe7724e1e31000abe07e2 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 30 Oct 2018 22:01:43 -0500
Subject: Majority Element done!

Oh yeah, I had so much fun with this one! It really worked my brain and
gave me better appreciation of Divide and Conquer and Merge Sort! Philip
Guo's PythonTutor site is amazing! It really helped me in debugging my
recursive function. Fun fun fun!---
 .../sources/MajorityElement.java                   | 77 ++++++++++++++++++++++
 .../tests/MajorityElementTest.java                 | 61 +++++++++++++++++
 2 files changed, 138 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/MajorityElement.java
 create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/MajorityElementTest.java

(limited to 'AlgoDesignAndTechniqueEdxJava')

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/MajorityElement.java b/AlgoDesignAndTechniqueEdxJava/sources/MajorityElement.java
new file mode 100644
index 0000000..7ef3977
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/MajorityElement.java
@@ -0,0 +1,77 @@
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.util.StringTokenizer;
+
+public class MajorityElement {
+
+    public static void main(String[] args) {
+        FastScanner scanner = new FastScanner(System.in);
+        int n = scanner.nextInt();
+        int[] a = new int[n];
+        for (int i = 0; i < n; i++) {
+            a[i] = scanner.nextInt();
+        }
+        if (getMajorityElement(a, 0, a.length -1) != -1) {
+            System.out.println(1);
+        } else {
+            System.out.println(0);
+        }
+    }
+    static class FastScanner {
+        BufferedReader br;
+        StringTokenizer st;
+
+        FastScanner(InputStream stream) {
+            try {
+                br = new BufferedReader(new InputStreamReader(stream));
+            } catch (Exception e) {
+                e.printStackTrace();
+            }
+        }
+
+        String next() {
+            while (st == null || !st.hasMoreTokens()) {
+                try {
+                    st = new StringTokenizer(br.readLine());
+                } catch (IOException e) {
+                    e.printStackTrace();
+                }
+            }
+            return st.nextToken();
+        }
+
+        int nextInt() {
+            return Integer.parseInt(next());
+        }
+    }
+
+	public static int getMajorityElement(int[] a, int left, int right) {
+		if (left == right)
+			return a[left];
+		int middle = (right - left) / 2;
+		int b = getMajorityElement(a, left, left + middle);
+		int c = getMajorityElement(a, left + middle + 1, right);
+		int d = conquer(a, b, c, left, right);
+		return d;
+	}
+
+	private static int conquer(int[] a, int b, int c, int left, int right) {
+		int countB = 0;
+		int countC = 0;
+		for (int i = left; i < right + 1; i++) {
+//		for (int i = 0; i < right + 1; i++) {
+			if (a[i] == b)
+				countB++;
+			if (a[i] == c)
+				countC++;
+		}
+		if (countB > (right - left + 1) / 2)
+			return b;
+		if (countC > (right - left + 1) / 2)
+			return c;
+		return -1;
+	}
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/MajorityElementTest.java b/AlgoDesignAndTechniqueEdxJava/tests/MajorityElementTest.java
new file mode 100644
index 0000000..b3b1773
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/MajorityElementTest.java
@@ -0,0 +1,61 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class MajorityElementTest {
+
+	@Test
+	void testGetMajorityElement0() {
+		int[] a = { 1, 1 };
+		assertEquals(1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+	}
+
+	@Test
+	void testGetMajorityElement1() {
+		int[] a = { 1, 2 };
+		assertEquals(-1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+	}
+
+	@Test
+	void testGetMajorityElement2() {
+		int[] a = { 1, 2, 1 };
+		assertEquals(1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+	}
+
+	@Test
+	void testGetMajorityElement3() {
+		int[] a = { 1, 2, 2 };
+		assertEquals(2, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+	}
+
+	@Test
+	void testGetMajorityElement4() {
+		int[] a = { 1 };
+		assertEquals(1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+	}
+
+	@Test
+	void testGetMajorityElement5() {
+		int[] a = { 1, 2, 2, 2 };
+		assertEquals(2, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+	}
+
+	@Test
+	void testGetMajorityElement() {
+		int[] a = { 2, 3, 9, 2, 2 };
+		assertEquals(2, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+	}
+
+	@Test
+	void testGetMajorityElement6() {
+		int[] a = { 1, 2, 3, 4 };
+		assertEquals(-1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+	}
+
+	@Test
+	void testGetMajorityElement7() {
+		int[] a = { 1, 2, 3, 1 };
+		assertEquals(-1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+	}
+
+}
-- 
cgit v1.2.3