arraylist Index des größten, zweit-,dritt-,...-größten Elemtens ausgeben

[Jagito]

Hi,
stehe vor folgendem Problem, für das ich noch keine Lösung (auch nicht im Internet) gefunden habe. Wahrscheinlich fehlen mir die richtigen Schlagworte.

Sei al eine arraylist, welche bspw. 7 Integer enhält, wobei keine Reihenfolge besteht, z.B. könnte die arraylist 4,56,23,1,45,2,3 sein.

Nun versuche ich eine Methode zu generieren, welche mir die Einträge der arraylist nach der Größe sortiert, mir aber nur die Indizes wiedergibt (so dass die arraylist unverändert bleibt) und ich später mit Hilfe der Indizes spezifisch auf einen Eintrag zugreifen kann.

d.h. wenn ich obiges Bsp fortsetze, wäre die Ausgabe (bei Sortierung von Maximum nach Minimum): 1,4,2,0,6,5,3 (die erste Eins, da die größte Zahl-56-an 2.ter Stelle steht)

Wie könnte ich dies implementieren?

 

[bygones]

liste kopieren in neue Liste, die dann sortieren, drüber iterieren und die jeweiligen objekte in der originalliste suchen (ueber get), das liefter dir die indizes und die kannste wieder in ne liste packen

 

[ARadauer]

Eine Klasse erstellen. Diese hat den Wert und den Index den der Wert im Array hat.
Über das Array iterierieren, für jeden Wert ein Objekt der klasse erstellen, dieses Objekt in eine Liste einfügen.
Die Klasse soll nun Compareable implementieren, dass anhand des Wertes sortiert. Nun die Liste sortieren und fertig...

 

[ARadauer]

ok was bygones sagt ist auch ganz nett ;-)

	public static void main(String[] args) {
		int[] values = {4,56,23,1,45,2,3} ;
		
		ArrayList<IndexValue> indexValues = new ArrayList<IndexValue>();
		for(int i = 0; i < values.length; i++)
			indexValues.add(new IndexValue(i, values[i]));
		
		Collections.sort(indexValues);
		
		for(IndexValue iv : indexValues){
			System.out.println(iv);
		}
	}

public class IndexValue  implements Comparable<IndexValue>{	

	
	private int value;
	private int index;	
	
	public IndexValue(int index, int value) {
		super();
		this.index = index;
		this.value = value;
	}
	
	public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value = value;
	}
	public int getIndex() {
		return index;
	}
	public void setIndex(int index) {
		this.index = index;
	}

	@Override
	public int compareTo(IndexValue o) {
		if(getValue()>o.getValue()){
			return 1;
		}else if(getValue()<o.getValue()){
			return -1;
		}
		return 0;
	}
	
	public String toString(){
		return index+" - "+value;
	}
	

}

 

[Jagito]

Danke euch Super. Werde den Code mal an meine Gegebenheiten anpassen.

 

[Landei]

Findet ihr das nicht eventuell ein klein wenig übertrieben?

Was haltet ihr davon:

    private static int[] indexBubbleSort(int[] data) {
        int[] indices = new int[data.length];
        for(int i = 0; i < data.length; i++) {
            indices[i] = i;
        }
        for(int i = data.length-1; i > 0; i--) {
            for(int j = 0; j < i; j++) {
               if(data[indices[j]] < data[indices[j+1]]) {
                   int temp = indices[j];
                   indices[j] = indices[j+1];
                   indices[j+1] = temp;
               }
            }
        }
        return indices;
    }

 

[Marco13]

Kommt drauf an, was man erreichen oder vermittlen will. Wenn ich z.B. ein Inf I.. oder II oder III-Tutor wäre, würde ich dem betreffenden Studenten Lösungen, bei denen die Laufzeit für das Finden der k größten von n Elemente im worst case n*k ist genauso um die Ohren hauen, wie eine, bei der das ganze schon bei k=1 im worst case n*n benötigt.... (Aber genaugenommen müßte man überprüfen, ob k<log(n) ist, um die optimale Lösung zu finden...)

 

[Landei]

Kommt drauf an, was man erreichen oder vermittlen will. Wenn ich z.B. ein Inf I.. oder II oder III-Tutor wäre, würde ich dem betreffenden Studenten Lösungen, bei denen die Laufzeit für das Finden der k größten von n Elemente im worst case n*k ist genauso um die Ohren hauen, wie eine, bei der das ganze schon bei k=1 im worst case n*n benötigt.... (Aber genaugenommen müßte man überprüfen, ob k<log(n) ist, um die optimale Lösung zu finden...)

Wenn Bubblesort über Indizes zu implentieren geht (und da war ich mir gar nicht so sicher), wird es so ähnlich auch mit anderen Sortierverfahren funktionieren. Ich denke jedenfalls, dass die oben vorgestellten Lösungen ziemlich umständlich sind.

 

[Marco13]

Ja, dagegen sag' ich ja auch gar nichts - aber BubbleSort hat eben im Worst case O(n^2). Das hier ist auch nicht viel komplizierter...

// Marco13 for [url]http://www.java-forum.org/java-basics-anfaenger-themen/90643-arraylist-index-groessten-zweit-dritt-groessten-elemtens-ausgeben.html[/url]
import java.util.*;

class ConnectedSortTest
{
    public static void main(String[] args)
    {
        final int array[] = {4,56,23,1,45,2,3};

        List<Integer> indices = new ArrayList<Integer>();
        for (int i=0; i<array.length; i++)
        {
            indices.add(i);
        }
        Comparator<Integer> comparator = new Comparator<Integer>()
        {
            public int compare(Integer i0, Integer i1)
            {
                return array[i1]-array[i0];
            }
        };

        Collections.sort(indices, comparator);
        System.out.println(indices);
    }
}

(IMHO sogar noch einfacher....) ...und liefert die komplette Indexliste in O(nlogn) - dann geht es nur noch um die Frage, ob man mehr oder weniger als logn indizes haben will...