Element lipsa3 c++

1

Am o mica problema…

Cerinta:

Ți se dă un șir de n numere întregi, reprezentând pachetele trimise și un alt șir cu n - m numere întregi, reprezentând pachetele care au ajuns cu succes până la tine. Elementele din cel de-al doilea vector vor fi în aceeași ordine ca și cele din primul, cu excepția a m elemente din primul șir care vor lipsi din al doilea. Identifică elementele lipsă, ținând cont că ele nu sunt neapărat pe poziții consecutive în primul șir.

Date de intrare

Pe prima linie se vor găsi numerele n și m, separate printr-un spațiu, iar pe următoarele două linii elementele celor două șiruri.

Date de ieșire

Programul va afișa pe ecran, în ordinea în care apar în primul șir, separate prin câte un spațiu, cele m elemente care lipsesc din al doilea șir. Dacă nu s-au pierdut date între cele două șiruri, programul va afișa pe ecran mesajul Nu s-au pierdut date .

Date de intrare

7 3
12 32 45 87 100 29 34
12 87 100 34

Date de iesire
32 45 29

Codul arata cam asa

#include <iostream>
using namespace std;
int main()
{
    int n, elementLipsa, m,i,j;
    cin >> n >> m;
    int a[100001];
    int b[100001];
    for ( i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for ( i = 1; i <= n - m; i++)
    {
        cin >> b[i];
    }
    for ( i = 1; i <= n; i++)
    {
        elementLipsa = 1;
        for ( j = 1; j <= n - m; j++)
        {
            if (a[i] == b[j])
            {
                elementLipsa = -1;
            }
        }
        if (elementLipsa == 1)
        {
            cout << a[i] << " ";
        }
    }

    cout<<"Nu s-au pierdut date";
    return 0;
}

Ideea este ca rezultatul este bun,dar orice fac imi arata si mesajul "Nu s-au pierdut date"iar cand testez pe compilatorul online unde trebuie sa trimit solutia,imi spune: Limita de timp depasita(adica la un moment dat intra intr-o bucla infinita,si nu imi dau seama unde).

Ma puteti ajuta va rog frumos(in c++ trebuie rezolvata problema)

2

Pai ce cauta acel cout<<"Nu s-au pierdut date";? Poti sa scrii orice acolo si il va afisa
Pune-l in primul if ca acolo verifici daca array-urile sunt egale, asta daca vrei sa afisezi mesajul.

LE: Poti sa stergi mesajul. Nu este nevoie de el.

Ai 2 for-uri imbricate, de unde poate iti rezulta o complexitate mai mare, deci timp mai lung de rulare pentru array-uri foarte mari. Poti sa folosesti solutia lui @serghei din topicul anterior.

3

Multumesc,acum am vazut raspunsul.Azi o sa testez cum mi-ai spus:)

4

Am incercat sa adaptez codul acesta:

#include <iostream>

using namespace std;
int main()
{
	long n;
	cout << "Input n: ";
	cin >> n;
	long a[1000];
	long b[1000];
	for (long i = 0; i < n; i++)
	{
		cout << "Input a" << i << " ";
		cin >> a[i];
	}
	for (long i = 0; i < n - 1; i++)
	{
		cout << "Input b" << i << " ";
		cin >> b[i];
	}
	//daca e un singur element atunci numai ala poate fi cel diferit
	if (n == 1)
	{
		cout << a[0];
		return 0;
	}

	//parcurgem sirul mai scurt si verificam in sirul mai lung
	for (long i = 0; i < n - 1; i++)
	{
		if (a[i] != b[i])
		{
			cout << a[i];
			return 0;
		}
	}

	//daca nu am gasit nimic si al doilea sir s-a terminat inseamna ca e ultimul element din primul
	cout << a[n-1];
	return 0;

Conform cerintei de mai sus,si nu am reusit deloc…am stat jumatate de zi si nu am reusit…ma poate ajuta cineva va rog frumos?

5

Daca vrei sa mergi pe aceeasi idee incearca sa parcurgi ambele siruri intr-un while cu un index pentru fiecare, cand elementele sunt egale avansezi in ambele, cand nu sunt egale avansezi doar in primul.

1 Like
6

Da cum pot sa parcurg ambele siruri doar cu un while?

7

Cred ca se rezolva mult mai usor,dar cu c++ meu de balta nu prea am cum…

#include <iostream>

using namespace std;

int main()
{
    int n,m,k,a[100],b[100],nrlipsa[100],z=0,index=0;
    cout<<"Introdu n:";
    cin>>n;
    cout<<"Introdu m:";
    cin>>k;
    m=n-k;
    cout<<"Introdu primul sir:";
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cout<<"Introdu al doilea sir:";
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    for(int i=0;i<n;i++){
        for(int j=index;j<m;j++){
            if(a[i] != b[j]){
                nrlipsa[z]=a[i];
                z++;
                break;
            }else{
                index++;
                break;
            }
        }
    }
    cout<<"Nr lipsa sunt:";
    for(int i=0;i<z;i++){
        cout<<nrlipsa[i]<<" ";
    }
    if(!z){
        cout<<"Nu s-au pierdut date."
    }
}
8

Am testat acum codul si functioneaza…daca il trimit pe compilatorul online de pe platforma unde lucrez,imi da 40/100 pcte si nu inteleg de ce x(…compilatorul testeaza si pe cazuri particulare si nu stiu care sunt alea

9

Se poate optimiza puțin.

Dacă șirurile au aceeași lungime, nu trebuie parcurse. Au ajuns toate pachetele.

In momentul in care au rămas același număr de elemente de parcurs in ambele șiruri poți sa te oprești.

Ceva de genul asta

#include <iostream>

using namespace std;

int main()
{
    // adaugi tu partea de input date
    int trimis[] = {0,1,2,3,4,5,6,7,8,9,10};
    int primit[] = {1,3,4,6,7,8};
    
    int n = sizeof(trimis)/sizeof(int);
    int m = sizeof(primit)/sizeof(int);

    if (n == m) {
        cout << "Nu s-au pierdut date";
    }
    
    int i = 0, j =0;
    
    while(i < n  || j < m ) {
        if (n - i == m - j) break; 
        if (trimis[i] != primit[j]) {
            cout << trimis[i] << " ";
        } else {
            j+=1;  
        }
        i+=1;
    }

    return 0;
}
1 Like
10

offtopic: un sfat pentru viitor, inteleg ca esti la inceput: obisnuieste-te sa scrii codul (variabile, functii, comentarii) in engleza. Outputul il scrii cum ai nevoie, dar codul in sine scrie-l in engleza.

3 Likes
11

Nu am reusit inca sa rezolv problema.La compilatorul de pe platforma imi scrie: Limita de timp depasita…cred ca e din cauza for-urilor