array werte vergleichen...

Hallo,

ich habe ein Array mit 6 LONG werten. Jetzt sind aber nur zwei dieser Werte NICHT doppelt. Wie kann ich diese beiden werte am besten ausfiltern?

beispiel:

array[0] = 0;
array[1] = 1;
array[2] = 2;
array[3] = 1;
array[4] = 2;
array[5] = 3;

In diesem Fall müssten also array[0] und array[5] gefiltert werden. Wie mach ich das effektiv?

Vielen Dank im Vorraus für jegliche Hilfe
Gruss
Desi

HumeSikkins

Wie kann ich diese beiden werte am besten ausfiltern?

Was genau meinst du mit ausfiltern?

Als Eingang für deinen Filter haben wir ein Array. Was soll raus kommen? Ein neues Array? Das alte Array verändert?

Etwas genauer musst du dein Problem schon spezifizieren.

Hallo HumeSikkins,

upps entschuldigung. Die beiden nicht doppelten Werte sollen den Variablen a und b übergeben werden die ich zuvor definiert haben.

LONG a=NULL,b=NULL;

...

Danke
Desi

Mirauder_Mo

die beiden, was soll pasieren wenn 3 nicht zweimal vorkommen ???

Es ist garantiert das 2 Zahlen doppelt sind und zwei Zahlen nicht!

So jetzt hab ichs auch selber raus. Das die Leute immer erst versuchen andere Sachen zu klären anstatt auf das eigentliche Problem einzugehen (hummeSikins hatte jedoch recht, die Info hatte tatsächlich von mir gefehlt, dachte jedoch das geht fixer hier...).

Na ja, hier letzendlich wie ich es gelöst habe. Falls jemand eine bessere Methode kennt, kann er Sie aber trotzdem hier reinschreiben, würde mich nämlich interessieren.

Danke trotz allem (war nicht bös gemeint mein obiges Kommentar).

LONG c=0,d=0;
bool next=FALSE;
for(LONG j=0;j<6;j++)
   for(LONG k=0;k<6;k++)
   {
	if(j==k) continue;
	if(v[j]==v[k]) break;
	if(k==5 || (k==4 && j==5)) 
	{
	    if(!next) 
	    {
		c=v[j];
		next=TRUE;
	    }
	    else 
	    {
		d=v[j];
	    }
	}
   }

Mirauder_Mo

bool ersteBestezt = false;

int a[SIZE];

int x,y;

for(int i=0; i<SIZE; ++i) {
  bool doppel=false;
  for(int j=i+1; j<SIZE; ++j) {
    if(a[i]==a[j]) doppel=true;
  }
  if(!doppel) {
    if(!ersteBesetzt){
    x=a[i];
    ersteBesetzt=true;}
  else y=a[i];
  }
}

meintest du sowas ??

[edit] ich hab deins net ganz verstanden. was macht die if abfrage "if(k==5...)" ??? auserdem machst den vergleich von zwei elementen immer doppelt, dadurch das du die 2. for schleife immer mit 0 initialisierst.

HumeSikkins

Hallo,
wenn man das Problem mal etwas allgemeiner betrachet, nach dem Motto:
"Gegeben ein Array der Länge n, gesucht alle Arraywerte, die in dem Eingangsarray nur genau einmal vorkommen", dann fallen mir spontan (im Sinne von ohne Computer, ohne Bücher nur mit Stift und Zettel im ICE sitzend) zwei Algorithmen ein:

vector<int> getUniqueValues(const int* arr, unsigned arrSize)
{
    vector<int> result;
    for (unsigned i = 0; i < arrSize; ++i)
    {
        unsigned j;
        for (unsigned j = 0 ; j < i + arrSize; ++j)
        {
            if (arr[i] == arr[j % arrSize])
                break;
        }
        if (j == i + arrSize)
            result.push_back(arr[i]);
    }
    return result;
}

Der Algo ist natürlich ziemlich mies, da furchtbar viele Vergleiche doppelt gemacht werden -> O(n^2)-Aufwand

Darf man das Ausgangsarray kaputtmachen, dann würde ich vorher sortieren:

vector<int> getUniqueValues(int* arr, unsigned arrSize)
{
    sort(arr, arr+arrSize);
    vector<int> result;
    unsigned first = 0;
    unsigned second = 1;
    while (second < arrSize)
    {
        if (arr[first] != arr[second])
        {
            result.push_back(arr[first++]);
            ++second;
        }
        else
        {
            ++second;
            while (arr[first] == arr[second]) ++second;
            first = ++second - 1;
        }
    }
    if (first < arrSize) 
        result.push_back(arr[first]);
    return result;
}

Das macht imo eine Komplixität von O(n*logn) für das sortieren + nochmal n (?) Vergleiche danach.

Meine Frage jetzt: Geht das nicht noch besser? Besonders für die Variante, die das Ausgangsarray ganz lässt?

PS: Ich habe die Algos nur auf Papier getestet (habe hier kein C++ Compiler) und da ich kein Buch zur Hand hatte, habe ich in der while-Schleife auch auf std::equal_range verzichtet. Nur falls ihr euch wundern solltet

japro

geht da nicht einfach sowas in der art:

sort(&array[0], &array[6]);
LONG *newend = unique(&array[0], &array[6]);

HumeSikkins

japro schrieb:

geht da nicht einfach sowas in der art:
sort(&array[0], &array[6]);
LONG *newend = unique(&array[0], &array[6]);

Ne. Unique macht aus einer *sortierten* Sequenz eine Sequenz in der jedes Element nur genau einmal vorkommt.
Das ist nicht das was gewünscht ist.
Am Beispiel:
Eingabe: {1,2,2,3,5,5} gesuchte Ausgabe: {1,3} Unique-Ausgabe: {1,2,3,5}

Mirauder_Mo

Hy, warum sagt mir niemand das mein code schlicht weg falsch ist Obwohl ich ihn für sehr effizient gehalten habe.

ich hab ihn modifiziert und hoffe das er so stimmt. ich hab zwar keine ahnung von vectoren, hab aber mal versucht das aus HumeSikkins code abzuleiten.

vector<int> getUniqueValues(int* arr, unsigned arrSize) {
  vector<int> result;
  bool * nichtDoppelt = new bool[arrSize};

  for(int i=0; i<arrSize; ++i) nichtDooppelt[i]=true;

  for(int i=0; i<arrSize; ++i) { 
    if(nichtDoppelt[i]){
      for(int j=i+1; j<arrSize; ++j) { 
        if(arr[i]==arr[j]) {
          nichtDoppelt[i]=false;
          nichtDoppelt[j]=false;
        } 
      }
    } 
  }
  for(int i=0; i<arrSize; ++i) 
    if(nichtDoppelt[i]) result.push_back(arr[i]);

  delete nichtDoppelt;
  return result;
}

ich denke das ist effizient und hoffentlich diesmal fehlerfrei

[edit] scheise, schon wieder ein fehler gemacht. jetzt muss es aber laufen. der vergleich von nichtDoppelt ist natürlich nur für den einzelnen durchlauf relevant und nicht als abbruckbedingung.

geschweigenden davon das return gefehlt hat.

HumeSikkins

ich denke das ist effizient und hoffentlich diesmal fehlerfrei

Ich befürchte nicht.
Eingabe: {1,2,2,3,4,4,1}. gewünschte Ausgabe -> 3
Bei dir kommz aber 3,4,4 raus, da die äußere Schleifenbedingung für i = 2 falsch wird, weil nichtDoppelt[2] dort bereits false ist.

Allerdings habe ich das wiederum nur mit Stift und Papier durchgerechnet. Kann also auch mist sein.

Mirauder_Mo

HumeSikkins schrieb:

Allerdings habe ich das wiederum nur mit Stift und Papier durchgerechnet. Kann also auch mist sein.

du hast richtig gerechnet. ich hatte auch keinen compiler darum bemüht sich das mal anzusehen. habs korigiert.

Versteh den ganzen Aufwand nicht.

[cpp]
for(int i=0;i<zahl.size();i++)
{
if(count(zahl.begin(),zahl.end(),zahl[i])==1) result.push_back(zahl[i]);
}

Nochmal besser lesbar.

for(int i=0;i<zahl.size();i++)
{
   if(count(zahl.begin(),zahl.end(),zahl[i])==1) result.push_back(zahl[i]);
}

Geschwindigkeitsoptimiert.

for(int i=0;i<zahl.size()&&result.size()<2;i++)
{
   if(count(zahl.begin(),zahl.end(),zahl[i])==1) result.push_back(zahl[i]);
}

Mirauder_Mo

Mein ansatz war es eher das ganze nicht nur richtig sonder auch schnell zu machen, und da kann der algorythmus von dir wohl nicht mithalten. nicht nur das es eine menge funktions aufrufe gibt, es werden auch zuviele unnötigen vergleiche gemacht.

z.b. bei einem array der größe 2 würde dein algorythmus erst das erste element mit dem zweiten vergleichen, und dann überflüssiger weise das zweite mit dem ersten.

@Mirauder_Mo

Mein Algorythmus kann sehr wohl mit deinem mithalten.
Trotz der unnötigen Vergleiche liegt mein Algorythmus von der Geschwindigkeit mit deinem auf einer Linie.
Habs auch als Funktion in deinem Stil getestet.
Ps.
Wenn dein Code in Hinblick auf Schnelligkeit gemacht wurde würde ich niemals einen Vector zurückgeben.

vector <int> getUniqueValues(int *arr,unsigned arrsize)
{
   vector <int> result;
   for(int i=0;i<arrsize&&result.size()<2;i++)
   {
      if(count(arr,arr+arrsize,arr[i])==1) result.push_back(arr[i]);
   }
   return result;
}

HumeSikkins

@_Stefan
Also meiner Meinung nach hat dein Algorithmus (kein y) die Komplexität O(n^2) und wenn ich mich recht erinnere war meine Frage, ob das nicht besser geht. Er zählt sogar unnötig weiter, da er ja nicht die Frage "gibt es mehr als einen" sondern "wieviele gibt es" beantwortet.
Könntest du mir mal erklären, was ich übersehe?

PS: Es ging mir um den Algorithmus nicht um die Effizienz der Vektor-Rückgabe.

Taurin

@Hume
Ich deine beiden Algos mal getestet. Die erste Variante (const int* arr)
scheint nicht zu funktionieren.

Ich hab' mal Mirauder_Mo's Version ein bissl verändert. Insbesondere die
Schleife am Ende war überflüssig.

vector<int> getUniqueValues(int* arr, unsigned arrSize) 
{ 
  vector<int> result; 

  bool * nichtDoppelt = new bool[arrSize]; 

  fill(nichtDoppelt, nichtDoppelt+arrSize, true);

  for(int i=0; i<arrSize; ++i) 
  {  
    if(nichtDoppelt[i])
    { 
      for(int j=i+1; j<arrSize; ++j) 
      {  
        if(arr[i]==arr[j]) 
        { 
          nichtDoppelt[i]=false;
          nichtDoppelt[j]=false; 
        }  
      } 
      if(nichtDoppelt[i]) result.push_back(arr[i]);
    }  
  } 

  delete nichtDoppelt; 
  return result; 
}