Seite 1 von 1

Search Second Largest Element

Verfasst: 14. Sep 2016 15:30
von Induktionsbeweis
Hallo Leute :)

ich versuche gerade die Nabla-Programmieraufgabe "Search Second Largest Element" zu Lösen. Eine verbindliche Anforderung an die Implementation ist "Die Anzahl der compare-Aufrufe darf n nicht überschreiten."
Ich weiß nicht, wie ich vorgehen soll, um diese Anforderung zu erfüllen. Hat evtl. jmd einen Denkanstoß?

Re: Search Second Largest Element

Verfasst: 14. Sep 2016 20:43
von Sabrina
public void searchSecondLargestElement() {
int i = 0;
setLargest(0);
setSecLargest(-1);
Comparator<T> c = getComp();
for(int i=0; i <= get.length(); i++) {
if (c.compare(getLargest(), getElement(i))) > 0 {
if(c.compare(getSecLargest(),getElement(i))) >= 0 {
}
else { //(c.compare(getSecLargest(),getElement(i)))<0
setSecLargest(getElement(i));
}
}
else if (c.compare(getLargest(), getElement(i))) < 0 {
setSecLargest(getLargest());
setLargest(getElement(i));
}
else { //(c.compare(getLargest(), getElement(i))) == 0
if (c.compare(getSecLargest(),getElement(i))) < 0 {
setSecLargest(getElement(i));
}
else { //(c.compare(getSecLargest(),getElement(i))) == 0
}
}
}
return getSecLargest();
}

Re: Search Second Largest Element

Verfasst: 14. Sep 2016 20:44
von Sabrina

Code: Alles auswählen

public void searchSecondLargestElement() {
	int i = 0;
	setLargest(0);
	setSecLargest(-1);
	Comparator<T> c = getComp();
	for(int i=0; i <= get.length(); i++) {
		if (c.compare(getLargest(), getElement(i))) > 0 {
			if(c.compare(getSecLargest(),getElement(i))) >= 0 {
			}
			else {	//(c.compare(getSecLargest(),getElement(i)))<0
				setSecLargest(getElement(i)); 
			}	
		}
		else if (c.compare(getLargest(), getElement(i))) < 0 {
			setSecLargest(getLargest());
			setLargest(getElement(i));
		}
		else {	//(c.compare(getLargest(), getElement(i))) == 0 
			if (c.compare(getSecLargest(),getElement(i))) < 0 {
				setSecLargest(getElement(i));
			}
			else {	//(c.compare(getSecLargest(),getElement(i))) == 0 
			}
		}
	}
	return getSecLargest();
}

Re: Search Second Largest Element

Verfasst: 14. Sep 2016 22:16
von Induktionsbeweis
Vielen Dank für die Antwort, allerdings vergleichst du in deinem Code ja über n mal :?

Re: Search Second Largest Element

Verfasst: 14. Sep 2016 23:54
von kci
wenn ich mir das array [10,1,2,3,4,5,6,7,8,9] vorstelle fällt mir auch kein weg ein wie ich mit n Vergleichen hinkomme

dieser code besteht den Test mit den maximalen Nutzungen von compare, vielleicht siehst du ja warum :lol:

Code: Alles auswählen

{
int length=getLength();
if(length>1){
    int j=0;
    while(getElem(j)==null){
        j++;
    }
    int k=j+1;
        while(getElem(k)==null){
        k++;
    }
    if(k<length){
    if(getComp().compare(getElem(j),getElem(k))>=0){
         setLargest(j);
         setSecLargest(k);
    }
    else{
         setLargest(k);
         setSecLargest(j);        
    }
    for(int i=k+1;i<length;i++){
        if(getElem(i)!=null){
        if(getComp().compare(getElem(getLargest()),getElem(i))<0){
            setSecLargest(getLargest());
             setLargest(i);
             }else if(getComp().compare(getElem(getSecLargest()),getElem(i))<0){
                setSecLargest(i); 
             
        }
        
    }
    } 
}
}
}

Re: Search Second Largest Element

Verfasst: 15. Sep 2016 00:09
von Induktionsbeweis
Danke :D

vielleicht ist auch in der Aufgabenstellung ein Fehler, mittlerweile bin ich nämlich ziemlich skeptisch, ob es überhaupt möglich ist, das Problem mit n(oder weniger) Vergleichen zu lösen.