C++ viena array values izdzēst no otra

[laucinieks]

Sveiki,

Tātad ir 2 array, pieņemsim viens ir -

int i[1, 2, 3];

un otrs

int d[1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

 

tātad vai ir kāda iespēja no array d izņemt array i vērtības? Pēc izņemšanas array d būtu jaizskatās -

d[4, 5, 6, 7, 8, 9, 10];

 

Ar cieņu,

L.

[codez]

ja masīvi ir sakārtoti, tad, glabā indeksu pirmajam pasīvam un indeksu, kur raksti jaunās vērtības otrajā masīvā.

Ej cauri otrajam masīvam, un palielini otrā masīva indeksu tikai tad, ja vērtība nesakrīt ar pirmā masīva vērtību:

 

#include <iostream>
using namespace std;
int main()
{
int a[]={1,3,5};
int an=sizeof(a)/sizeof(int);
int b[]={2,3,4,5,5,6,7,8};
int bn=sizeof(b)/sizeof(int);
int j=0, k=0;
for(int i=0;i<bn;i++){
   	while(j<bn and a[j]<b[i]) j++;
   	if (a[j]!=b[i]) {
       	b[k]=b[i];
       	k++;
   	}
}
for(int i=0;i<k;i++) cout << b[i] << " ";
cout << endl;
}

 

Laiks O(n);

 

Ja masīvi nav sakārtoti un ir jāievēro kārtība rezultējošam masīvam, tad sakārto pirmo masīvu un ej cauri otrā masīva elementiem un ar bināro meklēšanu meklē pirmajā sakritību, ja sakrītibās nav, atstāj elementu masīvā.

 

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[]={4,8,2};
int an=sizeof(a)/sizeof(int);
int b[]={6,3,8,5,2,8,5,7,5};
int bn=sizeof(b)/sizeof(int);
sort(a,a+an);
int k=0;
for(int i=0;i<bn;i++){
   	if (!binary_search(a,a+an,b[i])){
       	b[k]=b[i];
       	k++;
   	}
}
for(int i=0;i<k;i++) cout << b[i] << " ";
cout << endl;
}

 

Laiks O(n * log2(k))

k - pirmā masīva garums

n - otrā masīva garums

Edited December 5, 2011 by codez

[laucinieks]

Hmm, paldies! Īsti nesapratu, ko nozīmē tas Laiks O.

L.

[daGrevis]

Izpildes laiks (ņemot par pamatu abus masīvus).

[codez]

http://en.wikipedia.org/wiki/Time_complexity