如何找到具有最少步数的元素

Question

如何计算到达特定索引的向前和向后计数的最少步数？

列表是：

content = [1, 2, 3, 4, 5]

如果我从索引 0 开始并想知道要向前迭代多少步才能到达数字 4 我会得到 3，因为：

#0 #1 #2 #3
[1, 2, 3, 4, 5]

不过我也想倒过来知道，比如：

#0       #2 #1
[1, 2, 3, 4, 5]

在上面的示例中，最小步数是 2

另一个例子

content = ["A", "B", "C", "D", "E"]
start_index = 4 # "E"
to_find = "D"

 #1   #2   #3   #4   #0
["A", "B", "C", "D", "E"]
# Moving forward I'll start from "A" again until reache "D"

                #1   #0
["A", "B", "C", "D", "E"] # Moving backwards...

在上面的示例中，最小步数是 1

注意：目标元素是唯一的。

Answer 1

你可以这样做：

len(content) - content.index(4)

因为content.index(4)找到“forward”索引，然后“backward”索引等于从元素4到列表末尾的元素个数，与全部减去第一个 content.index(4).

如评论中所述，这会在列表中找到 first 出现的索引。为了找到最后一个（即从末尾开始的第一个），你可以这样做：

content[::-1].index(4) + 1

示例：

>>> content = ['a', 'b', 'c', 'b']
>>> len(content) - content.index('b')
3
>>> content[::-1].index('b') + 1
1

Answer 2

只需减少索引而不是增加索引。 Python 列表支持负索引

content = [1, 2, 3, 4, 5]
end_element = 4

i = 0
count = 0
while content[i] != end_element:
    i -= 1 
    count += 1

print(count) # 2

当然，当 end_element 不在您的列表中时，这会留下 IndexError: list index out of range 的可能性，但您可以很容易地处理该错误。

Answer 3

def minimal_steps(lst: list, num: int, start: int = 0):
    pos = lst.index(num)
    return min(abs(pos - start), len(lst) - abs(pos - start))

编辑：问题更新后更新答案。

Answer 4

无for循环解决方案：

content = ["A", "B", "C", "D", "E"]
start_index = 4 # "E"
to_find = "D"

c2 = content*2
forward = c2[start_index:].index(to_find)
backward = c2[::-1][len(content)-start_index-1:].index(to_find)

print('minimum steps:', min(forward, backward))

Answer 5

假设目标元素始终存在于数组中：

content = ["A", "B", "C", "D", "E"]
start_index = 4 # "E"
to_find = "D"

end_index = content.index(to_find)
d = end_index - start_index
forward  = d if d>=0 else len(content) + d
backward = -d if d<=0 else len(content) - d
print(min(forward, backward))

Answer 6

这里有一个简单的方法，首先偏移列表并使用开始list.index()方法：

content = [1, 2, 3, 4, 5]
start_index = 0
to_find = 4

temp = content[start_index:] + content[:start_index]

print(temp.index(to_find))           # Forward
print(temp[::-1].index(to_find) + 1) # Backward

输出：

3
2

例如#2：

content = ["A", "B", "C", "D", "E"]
start_index = 4
to_find = "D"

temp = content[start_index:] + content[:start_index]

print(temp.index(to_find))           # Forward
print(temp[::-1].index(to_find) + 1) # Backward

输出：

4
1

Answer 7

在我看来，这是一个模数问题：

content = ["A", "B", "C", "D", "E"]
start_index = 4 # "E"
to_find = "D"

length = len(content)

difference = content.index(to_find) - start_index

print(min(difference % length, -difference % length))

请注意，我们只搜索content 一次，不像一些解决方案，包括目前接受的解决方案，搜索content 两次!

如何找到具有最少步数的元素

How to find an element with the minimum number of steps

python

algorithm