diff options
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava/sources/MajorityElement.java')
-rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/MajorityElement.java | 77 |
1 files changed, 77 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; + } + +} |