summaryrefslogtreecommitdiff
path: root/PlaygroundCpp
diff options
context:
space:
mode:
authorHaidong Ji2018-11-16 20:50:55 -0600
committerHaidong Ji2018-11-16 20:50:55 -0600
commit5558c3b43f4e6c8501c218b8871cb353cbd9344f (patch)
tree02ab46efef7e5a6a2859e1dd026213087dcb42cf /PlaygroundCpp
parent952c14b4bad84fceb4a3ba812137729f35e936f1 (diff)
Majority Element finally done!
Wow, it took awhile to finish. Work has been busy and I haven't had time to hack...
Diffstat (limited to 'PlaygroundCpp')
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp112
1 files changed, 28 insertions, 84 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 39d31da..e9f516d 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,101 +1,45 @@
-#include <iostream>
-#include <cassert>
#include <vector>
+#include <iostream>
//#include <gtest/gtest.h>
using std::vector;
-int binary_search_recursive(const vector<long> &a, int low, int high, int key) {
- if (high < low) {
- return -1;
+int conquer(vector<int> &a, int b, int c, int left, int right) {
+ int countB = 0;
+ int countC = 0;
+ for (int i = left; i < right + 1; i++) {
+ if (a[i] == b)
+ countB++;
+ if (a[i] == c)
+ countC++;
}
- int mid = (low + (high - low) / 2);
-
- if (key == a[mid]) {
- return mid;
- } else if (key < a[mid]) {
- return binary_search_recursive(a, low, mid - 1, key);
- } else
- return binary_search_recursive(a, mid + 1, high, key);
+ if (countB > (right - left + 1) / 2)
+ return b;
+ if (countC > (right - left + 1) / 2)
+ return c;
+ return -1;
}
-//int binary_search_iterative(const vector<long> &a, int low, int high, int key) {
-// while (low <= high) {
-// int mid = (low + (high - low) / 2);
-// if (key == a[mid]) {
-// return mid;
-// } else if (key < a[mid]) {
-// high = mid - 1;
-// } else {
-// low = mid + 1;
-// }
-// }
-// return -1;
-//}
-
-int binary_search(const vector<long> &a, int x) {
- int left = 0, right = (int) a.size();
- return binary_search_recursive(a, left, right, x);
+int get_majority_element(vector<int> &a, int left, int right) {
+ if (left == right)
+ return a[left];
+ int middle = (right - left) / 2;
+ int b = get_majority_element(a, left, left + middle);
+ int c = get_majority_element(a, left + middle + 1, right);
+ int d = conquer(a, b, c, left, right);
+ return d;
}
-
-//int linear_search(const vector<int> &a, int x) {
-// for (size_t i = 0; i < a.size(); ++i) {
-// if (a[i] == x)
-// return i;
-// }
-// return -1;
-//}
-
-//test(binarysearch, search1) {
-// vector<long> a { 1, 5, 8, 12, 13 };
-// assert_eq(binary_search(a, 8), 2);
-//}
-//
-//test(binarysearch, search2) {
-// vector<long> a { 1, 5, 8, 12, 13 };
-// assert_eq(binary_search(a, 1), 0);
-//}
-//
-//test(binarysearch, search3) {
-// vector<long> a { 1, 5, 8, 12, 13 };
-// assert_eq(binary_search(a, 23), -1);
-//}
-//
-//test(binarysearch, search4) {
-// vector<long> a { 1, 5, 8, 12, 13 };
-// assert_eq(binary_search(a, 11), -1);
-//}
-//
-//test(binarysearch, search5) {
-// vector<long> a { 3, 5, 8, 12, 13 };
-// assert_eq(binary_search(a, 2), -1);
-//}
-//
-//test(binarysearch, search6) {
-// vector<long> a { 1, 5, 8, 12, 13 };
-// assert_eq(binary_search(a, 13), 4);
-//}
-//
-//test(binarysearch, search7) {
-// vector<long> a { 1, 5, 8, 12, 13 };
-// assert_eq(binary_search(a, 12), 3);
+//TEST(MajorityElement, test1) {
+// vector<int> a = { 1, 1 };
+// ASSERT_EQ(get_majority_element(a, 0, a.size()-1), 1);
//}
int main() {
int n;
std::cin >> n;
- vector<long> a(n);
- for (size_t i = 0; i < a.size(); i++) {
+ vector<int> a(n);
+ for (size_t i = 0; i < a.size(); ++i) {
std::cin >> a[i];
}
- int m;
- std::cin >> m;
- vector<long> b(m);
- for (int i = 0; i < m; ++i) {
- std::cin >> b[i];
- }
- for (int i = 0; i < m; ++i) {
- //replace with the call to binary_search when implemented
- std::cout << binary_search(a, b[i]) << ' ';
- }
+ std::cout << (get_majority_element(a, 0, n - 1) != -1) << '\n';
}