fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. using std::vector;
  5.  
  6. int get_majority_element(vector<int> &a, int left, int right) {
  7.  
  8.  
  9. 	int m;
  10. 	int majority_left, majority_right;      // majority element in either sub array
  11. 	int count_right = 0, count_left = 0;    // count for above
  12. 	int leftt, rightt;                      // endpoints
  13.  
  14. 	if (a.size() == 1) {
  15. 		return a[0];
  16. 	}
  17. 	else {
  18.  
  19. 		m = (left + right) / 2;  // calculate mid point
  20.  
  21. 		vector<int> b_left(m);
  22. 		vector<int> b_right(right - m);
  23.  
  24.  
  25. 		// get left sub array
  26. 		for (int i = 0; i < m; i++) {
  27. 			b_left[i] = a[i];
  28. 		}
  29.  
  30. 		// set new endpoints
  31. 		leftt = 0;
  32. 		rightt = m;
  33.  
  34. 		majority_left = get_majority_element(b_left, leftt, rightt);
  35.  
  36. 		for (int i = 0; i < right - m + 1; i++) {
  37. 			b_right[i] = a.at(m + i);
  38. 		}
  39.  
  40. 		leftt = m;
  41. 		rightt = right - m + 1;
  42.  
  43. 		majority_right = get_majority_element(b_right, leftt, rightt);
  44.  
  45. 		// if there is a majority element, count its frequency
  46.  
  47. 		if (majority_left != -1) {
  48. 			for (int i = 0; i < a.size(); i++) {
  49. 				if (a[i] == majority_left)
  50. 					count_left++;
  51. 			}
  52. 		}
  53.  
  54. 		if (majority_right != -1) {
  55. 			for (int i = 0; i < a.size(); i++) {
  56. 				if (a[i] == majority_right)
  57. 					count_right++;
  58. 			}
  59. 		}
  60.  
  61.  
  62. 		// if both elements in sub arrays are majority and they're different, there is no majority element
  63. 		if (count_left == count_right && majority_left != majority_right) {
  64. 			return -1;
  65. 		}
  66.  
  67. 		// check if either sub array has a majority element that occurs more than n/2 times
  68. 		else if (count_right > count_left && count_right > a.size() / 2) {
  69. 			return majority_right;
  70. 		}
  71. 		else if (count_left > count_right && count_left > a.size() / 2) {
  72. 			return majority_left;
  73. 		}
  74. 	}
  75.  
  76. 	return -1;
  77.  
  78. }
  79.  
  80.  
  81. int get_majority_fast(vector<int> &a, int left, int right) {
  82.  
  83. 	std::reverse(a.begin(), a.end());
  84.  
  85. 	int current = 0;
  86. 	int count;
  87. 	for (int i = 0; i < a.size(); i++) {
  88. 		current = a[i];
  89. 		count = 0;
  90. 		for (int j = 0; j < a.size(); j++) {
  91. 			if (a[j] == current)
  92. 				count++;
  93. 		}
  94. 		if (count > a.size() / 2)
  95. 			return 1;
  96. 	}
  97. 	return -1;
  98. }
  99.  
  100. int main() {
  101. 	//    std::cin >> n;
  102. 	//    vector<int> a(n);
  103. 	//    for (size_t i = 0; i < a.size(); ++i) {
  104. 	//        std::cin >> a[i];
  105. 	//    }
  106. 	//    std::cout << (get_majority_fast(a, 0, a.size()) != -1) << '\n';
  107.  
  108. 	while (true) {
  109. 		int one, two;
  110. 		int n = rand() % 100;
  111. 		std::cout << n << "\n";
  112. 		vector<int> a;
  113. 		for (int i = 0; i < n; ++i) {
  114. 			a.push_back(rand() % 100);
  115. 		}
  116.  
  117. 		one = get_majority_element(a, 0, a.size());
  118. 		two = get_majority_fast(a, 0, a.size() != -1);
  119.  
  120. 		if (one != two) {
  121. 			std::cout << "Wrong answer: " << one << ' ' << two << "\n";
  122. 			break;
  123. 		}
  124. 		else {
  125. 			std::cout << "OK\n";
  126. 		}
  127. 	}
  128. }
Runtime error #stdin #stdout #stderr 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
83
stderr
copy 
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 2) >= this->size() (which is 2)
https://ideone.com/CdXM7T
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!