c++ - Time Limit Exceeded in dealing with large arrays -
i'm trying solve this question:
as know varchas going on. foc wants organise event called finding occurrence.
the task simple :
given array a[1...n] of positive integers. there q queries. in queries given integer. need find out frequency of integer in given array.
input:
first line of input comprises of integer n, number of integers in given array. next line comprise of n space separated integers. next line q, number of queries. next q lines comprise of single integer occurrence supposed find out.
output:
output single integer each query frequency of given integer.
constraints:
1<=n<=100000
1<=q<=100000
0<=a[i]<=1000000
and code:
#include <iostream> using namespace std; int main() { long long n=0; cin >> n; long long a[1000000]; (int i=1;i<=n;i++) { cin >> a[i]; } long long q=0; cin >> q; while (q--) { long long temp=0,counter=0; cin >> temp; (int k=1;k<=n;k++) { if (a[k]==temp) counter++; } cout << "\n" << counter; temp=0; counter=0; } homecoming 0; }
however, encountered 'time limit exceeded' error. suspect due failure handle big values in arrays. tell me how handle such big size arrays?
the failure in algorithm itself, note each query, traverse whole array. there 100,000 queries , 100,000 elements. means @ worse case you're traversing 100,000 * 100,000 elements = 10,000,000,000 elements, won't finish in time. if analyze complexity using big-o notation, algorithm o(nq)
, slow problem, since n*q
large.
what you're supposed calculate scores before query made, store in array (this why range of a[i]
given. should able traversing array only once. (hint: don't need store input array, can count directly).
by doing this, algorithm o(n)
, , since n
little plenty (as rule of thumb, less 1 1000000 small), should finish in time.
then can reply each query instantly, making programme fast plenty under time limit.
another thing can improve info type of array. value stored in array won't larger 1 million, , don't need long long
, uses more memory. can utilize int
.
c++ arrays algorithm
No comments:
Post a Comment