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 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