diff options
Diffstat (limited to 'PlaygroundCpp')
| -rw-r--r-- | PlaygroundCpp/Sources/Playground.cpp | 112 |
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'; } |