Python如何设计暴力算法实现数组X与Y同字符单元格配对

你的代码是否属于暴力解法？ #

你现有的代码属于标准的暴力解法。
Python内置的list.index()方法底层就是遍历整个列表查找匹配元素，你的代码外层循环遍历x数组共n次，每次调用y.index()平均需要遍历n/2个元素，整体时间复杂度为O(n²)，完全符合暴力解法的特征。

如果是学习用途需要更直观展示暴力法的双重循环逻辑，可以把隐式的index调用改成显式的嵌套循环，运行效果和你现有代码完全一致：

x = ["O", "L", "M", "S", "N", "J", "P", "T", "I", "R", "H", "G"]
y = ["S", "N", "H", "P", "T", "I", "O", "R", "L", "M", "G", "J"]

for i, x_char in enumerate(x):
    for j, y_char in enumerate(y):
        if x_char == y_char:
            print(f"x[{i}] == y[{j}]")
            break

是否需要重新编写暴力解法？ #

不需要重新写，你现有的代码就是可用的暴力实现，上面的显式嵌套循环版本只是更方便理解暴力法的执行逻辑，二者的时间复杂度和运行结果没有区别。

优化算法实现 #

优化的核心思路是用哈希表（字典）预存储y数组的字符到下标的映射，把每次查找的时间复杂度从O(n)降到O(1)，整体时间复杂度可以降到O(n)，实现代码如下：

x = ["O", "L", "M", "S", "N", "J", "P", "T", "I", "R", "H", "G"]
y = ["S", "N", "H", "P", "T", "I", "O", "R", "L", "M", "G", "J"]

# 仅遍历一次y数组构建映射表
y_char_index = {char: idx for idx, char in enumerate(y)}
# 遍历x数组直接查表得到对应下标
for i, char in enumerate(x):
    print(f"x[{i}] == y[{y_char_index[char]}]")

如果数组中存在重复字符，只需要把映射表的值改为存储对应下标的列表，匹配时按顺序取用即可。

内容的提问来源于stack exchange，提问作者HoLee