Xin chào mọi người, em đang học về sorting và time complexity,em đang làm bài toán thế này: trả về 1 nếu mảng có chứa element nào nhiều hơn 50%, trả về 0 nếu không có.
Ví dụ như là:
5
2 3 9 2 2
thì sẽ return là 1 vì có tần suất của 2 > 50%
Đây là code của em
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int get_majority_element(vector<int> &a, int left, int right) {
//write your code here
if (a.size() == 0) return -1;
for (int i = 0; i < a.size(); i++)
{
for (int j = i + 1; j < a.size(); j++)
{
if (a[i] > a[j])
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
int count = 1;
int run = 1;
int last_run = a[0];
while (run < a.size())
{
if (a[run] == a[last_run])
{
count++;
}
else if (count > a.size() / 2) return 1;
else count = 1;
last_run = run;
run++;
}
if (count > a.size() / 2) return 1;
else return -1;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (size_t i = 0; i < a.size(); ++i) {
cin >> a[i];
}
cout << (get_majority_element(a, 0, a.size()) != -1) << '\n';
return 0;
}
Cho em hỏi code này của em có phải có time complexity là O(n.logn) không ạ? Vì code này nộp lên system thì nó bảo time limit exceed.
Nếu code này của em không hiệu quả về mặt thời gian thì chỉ em cách tiếp cận khác với ạ.
Trong bài hướng dẫn hình như có chỉ theo hướng merge sorted nhưng mà em chưa làm được. Mong mọi người giúp em, em xin cảm ơn ạ. :3
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?