Ottenere liste da una matrice

Un approccio è quello di mappare pigramente dai valori degli elementi alle liste con un dizionario. Alla prima apparizione dell'elemento, crea una lista. Nelle apparizioni future, riusare la lista corrispondente.

Se stai bene eseguendo due passaggi sull'input e non vuoi dizionari associativi, mantieni un elenco degli elenchi di offset e mantieni una mappatura di array dal valore dell'elemento all'indice della lista.

[(0,0), (1,1), (2,2), (3,3), (4,n/a), (5,4)]

Ciò causerà un'ulteriore indiretta sulla ricerca di elementi, ma potrebbe valerne la pena se ti aspetti una scarsità di valori. A questo punto di complessità, basta usare un dittico di liste già a meno che tu non abbia qualcosa contro le dicts.

Penso che il tuo approccio sia perfetto.

Sei preoccupato di ottenere 5 elenchi perché il numero più grande è 5, quindi puoi usare una mappa con il valore. Le chiavi della mappa sono i valori univoci dell'array.

Ecco un suggerimento concreto di codice in JavaScript. Puoi provarlo facilmente in qualsiasi console di debug del browser, basta copiarlo nella console:

// 1. Create a test array
var mainList = [5,0,3,5,2,5,3];

// 2. To get a map, we need some unique() function for an array:
function unique(rawArray) {
    var arr = [];
    for(var i = 0; i < rawArray.length; i++) {
        if(arr.indexOf(rawArray[i]) < 0) {
            arr.push(rawArray[i]);
        }
    }
    return arr; 
}

// At this point, you get for mainList:
// [5, 0, 3, 5, 2, 5, 3]

// And for unique(mainList);:
// [5, 0, 3, 2]

// 3. Now we create a function to get the index lists:
function createMaps(uniqueList, mainList) {

    // Create and init maps.
    var maps = {};

    for (var u=0; u<uniqueList.length; u++) {
        // Create a map entry and init it with an array.
        maps[uniqueList[u]] = [];

        // Fill the array with indices.
        for (var i=0; i<mainList.length; i++) {
            if (mainList[i] == uniqueList[u]) {
                maps[uniqueList[u]].push(i);
            }
        }
    }

    return maps;
}

// 4. Now let's put the thing together:
var uniqueList = unique(mainList);
var maps = createMaps(uniqueList, mainList);
// (end of script) 

Maps apparirà come segue:

Object {0: Array[1], 2: Array[1], 3: Array[2], 5: Array[3]}
0: Array[1]
    0: 1
2: Array[1]
    0: 4
3: Array[2]
    0: 2
    1: 6
5: Array[3]
    0: 0
    1: 3
    2: 5

Che è esattamente ciò che desideri. Vedi, la tua idea va bene.

Infine, hai menzionato un modo "più efficiente". Questo non è molto specifico. Per ottenere risposte concrete, prova a mettere alla prova la tua idea rispetto agli scenari:

• Che cosa succede a tutti gli elenchi di indici se rimuovi un valore dall'elenco principale? - > Molte liste devono essere aggiornate.
• dito: cosa succede a tutti gli elenchi di indici se aggiungi / inserisci / scambia ... i valori nell'elenco principale?
• Com'è la performance della costruzione di una serie di liste?
• Che cosa succede se desideri combinare i valori per gli indici (ad esempio, come hai combinato gli indici in una tabella SQL relazionale)? Quanta resistenza provi dal tuo modello?

e così via. In questo modo, vedrai diversi aspetti di "efficiente".

Questo è il mio approccio. Probabilmente lo stesso degli altri, ma in Java :) Effettuiamo iterazioni su tutti gli input, cercare nella nostra mappa se abbiamo già creato un elenco per questo valore di input, altrimenti creeremo una nuova lista. Quindi aggiungiamo semplicemente l'indice del valore alla lista.

public Map<Integer, List<Integer>> uniqueList(int...input) {
    Map<Integer, List<Integer>> resultMap = new HashMap<>();
    for(int i = 0; i<input.length; i++) {
        List<Integer> resultList = resultMap.get(input[i]);
        if(resultList == null) {
            resultList = new ArrayList<>();
            resultMap.put(input[i], resultList);
        }
        resultList.add(i);
    }
    return resultMap;
}

Questa è un'eccellente opportunità per una struttura dati ricorsiva che utilizza il polimorfismo. Vorrei fare una lista ordinata di elenchi ordinati. Doppia lista concatenata implementata con un inserto ordinato a bolle. L'elenco di backplane dovrebbe contenere nodi con una voce di dati e una voce di elenco. Gli elenchi secondari necessitano solo di voci di dati nei suoi nodi.