Код:
for (int i=0; i<arr.length; i++) // Loop A
{
for (int j=i; j<arr.length;j++) // Loop B
{
for (int k=i+1; k<=j; k++) // Loop C
{
// ..
}
}
}
Асимптотический анализ на Big-O:
Loop A: Time = 1 + 1 + 1 + .. 1 (n times) = n
Loop B+C: Time = 1 + 2 + 3 + .. + m = m(m+1)/2
Time = SUM { m(m+1)/2 | m in (n,0] }
Time < n * (n(n+1)/2) = 1/2 n^2 * (n+1) = 1/2 n^3 + 1/2 n^2
Time ~ O(n^3)
Как насчет этого?
>>> tuple_list = [("pineapple", 5), ("cherry", 7), ("kumquat", 3), ("plum", 11)]
>>> [x for x, y in enumerate(tuple_list) if y[1] == 7]
[1]
>>> [x for x, y in enumerate(tuple_list) if y[0] == 'kumquat']
[2]
Как указано в комментариях, при этом будут найдены все совпадения. Чтобы получить только первое, вы можете сделать:
>>> [y[0] for y in tuple_list].index('kumquat')
2
В комментариях есть хорошее обсуждение разницы в скорости между всеми опубликованными решениями. Я могу быть немного предвзятым, но я бы лично придерживался однострочника, поскольку скорость, о которой мы говорим, довольно незначительна по сравнению с созданием функций и импортом модулей для этой проблемы, но если вы планируете делать это в очень большом количестве элементов, возможно, вы захотите просмотреть другие предоставленные ответы, поскольку они быстрее, чем то, что я предоставил.
Список через некоторое время понимание становится беспорядочным.
from operator import itemgetter
def collect(l, index):
return map(itemgetter(index), l)
# And now you can write this:
collect(tuple_list,0).index("cherry") # = 1
collect(tuple_list,1).index("3") # = 2
# Stops iterating through the list as soon as it finds the value
def getIndexOfTuple(l, index, value):
for pos,t in enumerate(l):
if t[index] == value:
return pos
# Matches behavior of list.index
raise ValueError("list.index(x): x not in list")
getIndexOfTuple(tuple_list, 0, "cherry") # = 1
Одна из возможностей - использовать функцию itemgetter из модуля operator
:
import operator
f = operator.itemgetter(0)
print map(f, tuple_list).index("cherry") # yields 1
Вызов itemgetter
возвращает функция, которая будет выполнять эквивалент foo [0]
для всего, что ей передано. Используя карту
, вы затем применяете эту функцию к каждому кортежу, извлекая информацию в новый список, для которого вы затем вызываете index
как обычно.
map(f, tuple_list)
эквивалентно:
[f(tuple_list[0]), f(tuple_list[1]), ...etc]
], что, в свою очередь, эквивалентно:
[tuple_list[0][0], tuple_list[1][0], tuple_list[2][0]]
, что дает:
["pineapple", "cherry", ...etc]
Вы можете сделать это с помощью понимания списка и index ()
tuple_list = [("pineapple", 5), ("cherry", 7), ("kumquat", 3), ("plum", 11)]
[x[0] for x in tuple_list].index("kumquat")
2
[x[1] for x in tuple_list].index(7)
1