Răspuns :
Partea aceasta:
for (i=1; i<=n;i++)
for (j=1; j<=n;j++)
for (k=1; k<=n;k++)
Are complexitate O([tex]n^3[/tex]), adica se executa de [tex]n^3[/tex] ori, ceea ce nu este foarte eficient, asta ar fi cauza pentru limitele de timp depasite.
Partea aceasta:
if (a[i]==b[j]==c[k])
Nu face ceea ce pare sa faca.Compilatorul o va evalua ca "if((a[i] == b[j]) == c[k])" sau ca "if (a[i] == (b[j] == c[k]))"
O alta diferenta mica este declararea vectorilor in afara main-ului, astfel se vor initializa in alta parte a memoriei, pentru care sunt alocati cei 2MB din problema, spre deosebire de initializarea in stiva (pentru care este alocat doar 1MB), ceea ce poate duce la depasirea limitei de memorie.
O mica diferenta in pasii cautarii celui mai mic element comun pentru a nu depasi limita de timp:
1.Incepe cu cei trei indici i,j si k de la 1.
2.Incepe o bucla cat timp, care se va executa cat timp a[i], b[j] si c[k] nu sunt egale, conditia fiind (a[i] != b[j] || b[j] != c[k])
3.Daca al i-lea element din a este mai mic decat al j-lea element din b sau al k-lea element din c, incrementeaza i
4.Daca al j-lea element din b este mai mic decat al i-lea element din a sau al k-lea element din c, incrementeaza j
5.Daca al k-lea element din c este mai mic decat al i-lea element din a sau al j-lea element din b, incrementeaza k
6. Daca i, j sau k a ajuns in afara vectorului(i > n, j > n sau k > n) atunci scrie -1 si opreste executia
7. Dupa executarea buclei de la 2, afiseaza elementul a[i], b[j] sau c[k]. Deoarece toate sunt egale, nu face nicio diferenta.
Codul cu toate aceste modificari este:
#include <iostream>
using namespace std;
int a[100005],b[100005],c[100005];
int main()
{
int n,i,j,k;
cin >>n;
for (i=1; i<=n;i++)
cin >>a[i];
for (i=1; i<=n;i++)
cin >>b[i];
for (i=1; i<=n;i++)
cin >>c[i];
i = j = k = 1;
while(a[i] != b[j] || b[j] != c[k]){
if(a[i] < b[j] || a[i] < c[k])
i++;
if(b[j] < a[i] || b[j] < c[k])
j++;
if(c[k] < a[i] || c[k] < b[j])
k++;
if(i > n || j > n || k > n){
cout<<-1;
return 0;
}
}
cout << a[i];
return 0;
}
e testat pe pbinfo acum, a luat 100, văd că se mai poate eficientiza dar îl postez în varianta care a tecut testarea şi am folosit interclasare
#include <iostream>
using namespace std;
int a[100001], b[100001], c[100001], d[100001], n, i, j, p, gasit, comun;
int main()
{
cin >> n;
for (i=0; i<n; ++i)
cin >> a[i];
for (i=0; i<n; ++i)
cin >> b[i];
for (i=0; i<n; ++i)
cin >> c[i];
i = 0 , j = 0;
p = 0;
while(i < n && j < n)
if(a[i] < b[j])
{ ++i;}
else
{ if (a[i]==b[j]) { ++j; d[p++]=a[i++]; }
else ++j;
}
while(i < n)
d[p ++] = a[i ++];
while (j < n)
d[p ++] = b[j ++];
i=0; j=0; gasit=0;
while (i<n && j<p && gasit==0)
{
if (c[i]<d[j])
{ ++i; }
else
{
if (c[i]==d[j]) { gasit=1; comun=c[i]; break;}
else { ++j; }
}
}
if (gasit) cout << comun;
else cout << -1;
}
Vă mulțumim că ați ales să vizitați platforma noastră dedicată Informatică. Sperăm că informațiile disponibile v-au fost utile. Dacă aveți întrebări suplimentare sau aveți nevoie de sprijin, nu ezitați să ne contactați. Vă așteptăm cu drag și data viitoare! Nu uitați să adăugați site-ul nostru la favorite pentru acces rapid.