Practice/MajorityElement.java at master · lummish/Practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
public class MajorityElement {

	public static Integer[] major(Object[] ar, int start, int end) {

		int sz = end - start;

		if (sz > 1) {

			int mid = start + (sz / 2);
			Integer[] left = major(ar, start, mid);
			Integer[] right = major(ar, mid, start + sz);

			/* for debugging
			printAr(ar, start, mid);
			printAr(ar, mid, start + sz);
			System.out.println("Start: " + start + ", End: " + mid + ", Left: " + left[0]);
			System.out.println("Start: " + mid + ", End: " + (start + sz) + ", Right: " + right[0]);
			*/

				if (left[0] == null && right[0] == null)

					return new Integer[] {null, (Integer) 0};

				else {

					if (left[0] == null && right[0] != null)

						return new Integer[] {right[0], (Integer) 1};

					else if (right[0] == null && left[0] != null)

						return new Integer[] {left[0], (Integer) 1};

					else {

						if (left[0] != right[0])

							if (left[1] == right[1])

								return new Integer[] {null, (Integer) 0};

							else

								if (left[1] == 2)

									return new Integer[] {left[0], (Integer) 1};

								else

									return new Integer[] {right[0], (Integer) 1};

						else

							return new Integer[] {left[0], (Integer) 2};

					}
				}
		}

		else return new Integer[] {(Integer) ar[start], (Integer) 1};
	}
	public static void printAr(Object[] ar, int st, int end) {

		for (int i = st; i < end; i++) System.out.print(ar[i] + " ");

		System.out.println();

	}

	public static void printOut(Object[] ar) {

		System.out.print("I/P: ");
		printAr(ar, 0, ar.length);

		Integer[] maj = major(ar, 0, ar.length);
		String res = "";

		if (maj[1].equals((Integer) 2)) {
			res += maj[0];
		}

		else {
			int count = 0;

			for (int i = 0; i < ar.length; i++) {
				if (ar[i] == maj[0]) count++;
			}

			if (count > ar.length/2) res += maj[0];
			else res += "none";
		}

		System.out.println("O/P: " + res);
	}
	public static void main(String[] args) {

		Integer[] in = new Integer[args.length];

		for (int i = 0; i < args.length; i++) {
			in[i] = Integer.parseInt(args[i]);
		}

		printOut(in);

	}
}