Obtention d'indices uniques de valeurs minimales dans des listes multiples

Question

J'ai du mal à me faire une idée de ce problème.

Disons que j'ai n listes contenant chacune n éléments. Pour chaque liste, je dois trouver l'indice de la valeur minimale et les stocker dans une nouvelle liste. C'est assez facile.

Le problème est que deux ou plusieurs valeurs de ma liste d'index peuvent être égales. J'ai besoin d'une liste avec des valeurs uniques. Si deux valeurs (ou plus) sont égales, je veux donner la priorité à la valeur d'index qui provient de la plus petite valeur minimale.

Exemple :

myLists = []
myLists.append([113.6, 12262.6, 21466.7, 141419.9])      # list 1
myLists.append([122284.8, 111161.8, 106581.1, 141419.9]) # list 2
myLists.append([25427.9, 13694.0, 5148.9, 141419.9])     # list 3
myLists.append([21354.9, 10599.2, 0.1, 141419.9])        # list 4

Cela me donnerait la liste d'index [0,2,2,2]. Sur la base de la deuxième valeur dans les listes 2, 3 et 4, je vois que la plus petite est dans la liste 4, donc ma liste d'index devrait ressembler à [0, ?,?,2].

Pour aller plus loin, je dois remplir les points d'interrogation avec les valeurs 1 et 3, mais lesquelles vont où ? Après inspection, je constate que puisque 13694,0 (indice 1 de la liste 3) est plus petit que 111161,8 (indice 1 de la liste 2) et que les valeurs du troisième indice de chaque liste sont égales, je dois choisir l'indice 1 de la liste 3.

Cela signifie que ma nouvelle liste d'index est [0, ?,1,2]. Comme il ne reste plus qu'un point d'interrogation, je le remplis avec 3, ce qui donne [0,3,1,2].

La plupart des listes seront petites, donc le temps de fonctionnement n'est pas vraiment un problème ici.

Answer 1

J'ai fusionné toutes les listes sous la forme de 3 tuples membres (valeur, indice de la liste dans mesListes, indice de la valeur dans la liste) et l'a trié par valeur. La complexité temporelle de mon code est nlog(n) .

myLists = []
myLists.append([113.6, 12262.6, 21466.7, 141419.9])  # list 1
myLists.append([122284.8, 111161.8, 106581.1, 141419.9])  # list 2
myLists.append([25427.9, 13694.0, 5148.9, 141419.9])  # list 3
myLists.append([21354.9, 10599.2, 0.1, 141419.9])  # list 4

merged_list = list()

for index1, ls in enumerate(myLists):
    for index2, x in enumerate(ls):
        merged_list.append((x, index1, index2))

merged_list.sort()

st = set()  #to store already added indices

res = [-1 for i in range(len(myLists))]

for x, y, z in merged_list:
    if res[y] != -1 or z in st:
        continue
    res[y] = z
    st.add(z)

print(res)

Sortie -

[0, 3, 1, 2]