summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-10-30 22:01:43 -0500
committerHaidong Ji2018-10-30 22:01:43 -0500
commit81692fe3e2b51ba1dfffe7724e1e31000abe07e2 (patch)
tree42076bd51b7bef0bb696f86f598962195c7d5be7
parentb75fb4d4a4503dac26efa4380eb38f89c010bb19 (diff)
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!
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/MajorityElement.java77
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/MajorityElementTest.java61
2 files changed, 138 insertions, 0 deletions
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));
+ }
+
+}