I stuck at a problem ,It was a basically implementation problem ,It passed all the test cases But I have doubt regarding its time complexity.↵
↵
~~~~~↵
for (int i = 0; i < 1e6 + 100; i++) {↵
sort(v[i].begin(), v[i].end());↵
}↵
~~~~~↵
↵
The time complexity of this loop seems to be O(nn*n*logn) .Then It should definitely fail because n value can be 10^6.Even O(n*n) fail for such higher value of n,I have seen already so many times on codeforces.↵
↵
What is its correct time complexity??↵
↵
[Problem link](http://codeforces.com/contest/558/problem/B)↵
↵
Please forgive me if it is too basic!↵
↵
↵
↵
↵
~~~~~↵
#include <iostream>↵
#include <cmath>↵
#include <algorithm>↵
#include <vector>↵
#include <cstring>↵
using namespace std;↵
const int N = 1e6 + 100;↵
vector<int> a, f(1e6 + 100);↵
vector<int>v[N];↵
int main() {↵
int n;↵
cin >> n;↵
a.resize(n);↵
int mx = -1;↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
f[a[i]]++;↵
v[a[i]].push_back(i);↵
mx = max(mx, f[a[i]]);↵
}↵
for (int i = 0; i < 1e6 + 100; i++) {↵
sort(v[i].begin(), v[i].end());↵
}↵
int diff = INT_MAX;↵
int ans[2];↵
for (int i = 0; i < 1e6 + 100; i++) {↵
if (f[i] == mx) {↵
int temp = v[i][v[i].size() - 1] - v[i][0];↵
if (diff > temp) {↵
diff = temp;↵
ans[0] = v[i][0];↵
ans[1] = v[i][v[i].size() - 1];↵
}↵
}↵
}↵
cout << ans[0] + 1 << " " << ans[1] + 1;↵
↵
}↵
~~~~~↵
↵
↵
~~~~~↵
for (int i = 0; i < 1e6 + 100; i++) {↵
sort(v[i].begin(), v[i].end());↵
}↵
~~~~~↵
↵
The time complexity of this loop seems to be O(n
↵
What is its correct time complexity??↵
↵
[Problem link](http://codeforces.com/contest/558/problem/B)↵
↵
Please forgive me if it is too basic!↵
↵
↵
↵
↵
~~~~~↵
#include <iostream>↵
#include <cmath>↵
#include <algorithm>↵
#include <vector>↵
#include <cstring>↵
using namespace std;↵
const int N = 1e6 + 100;↵
vector<int> a, f(1e6 + 100);↵
vector<int>v[N];↵
int main() {↵
int n;↵
cin >> n;↵
a.resize(n);↵
int mx = -1;↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
f[a[i]]++;↵
v[a[i]].push_back(i);↵
mx = max(mx, f[a[i]]);↵
}↵
for (int i = 0; i < 1e6 + 100; i++) {↵
sort(v[i].begin(), v[i].end());↵
}↵
int diff = INT_MAX;↵
int ans[2];↵
for (int i = 0; i < 1e6 + 100; i++) {↵
if (f[i] == mx) {↵
int temp = v[i][v[i].size() - 1] - v[i][0];↵
if (diff > temp) {↵
diff = temp;↵
ans[0] = v[i][0];↵
ans[1] = v[i][v[i].size() - 1];↵
}↵
}↵
}↵
cout << ans[0] + 1 << " " << ans[1] + 1;↵
↵
}↵
~~~~~↵
↵