在多个列表中获取最小值的唯一索引

Kallen 发表于 Dev

卡伦

我在解决这个问题时遇到了一些麻烦。

假设我有n个列表，每个列表包含n个元素。对于每个列表，我需要找到最小值的索引并将其存储在新列表中。这很容易。

问题是，我的索引列表中的两个或多个值可能相等。我需要一个具有唯一值的列表。如果两个（或多个）值相等，则我想优先考虑来自Smalles最小值的索引值。

例子：

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

这将给我索引列表[0,2,2,2]。基于列表2、3和4中的第二个值，我看到最小的是列表4，因此我的索引列表应看起来像[0，？，？，2]。

更进一步，我需要用值1和3填写问号，但是哪去了？通过检查，我发现由于13694.0（列表3的索引1）小于111161.8（列表2的索引1）并且每个列表中的第三个索引值相等，因此我应该从列表3中选择索引1。

这意味着我的新索引列表为[0，？，1,2]。仅剩一个问号，我用3填充。这得到[0,3,1,2]。

该列表通常很小，因此运行时间在这里并不是真正的问题。

韦当·梅塔（Vedang Mehta）

我以3个成员元组的形式合并所有列表（值，myLists中列表的索引，列表中值的索引）并按值对它进行排序。我的代码的时间复杂度为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)