是否有一种算法可以识别一组中相差一个数字的数字？
Is there an algorithm for identifying numbers in a set which are different by one digit?
在一组大小为 n 的六位数字中，是否有一种算法可以识别该组中相差一个数字的数字，而无需直接将每个元素与其他元素进行比较？是否可以在不到 O(n!) 的时间内完成此操作？
例如，在下面的一组数字中：
789000
889000
543200
125894
156795
146795
789000和889000相差一位数。 156795 和 146795 也相差一位数。算法需要识别这些数字。
直截了当的解决方案是渐近最优的：
def elements_one_apart(the_set):
result = set() # create a new set
for x in the_set:
for y in numbers_different_from_x_by_one_digit(x):
if y in the_set:
result.add(x)
break # skip to the next value of x
return result
外循环迭代the_set的n个元素，内循环最多迭代y的6 * 9 = 54个值。所以内层循环的迭代次数为O(n).
如果使用 hash-set data structure，in 和 add 操作各需要 O(1) 时间。所以总的时间复杂度是O(n)。如果输入不是hash-set，那么可以在O(n)时间内转换成hash-set，所以算法还是O(n)
没有解决方案可能比 O(n) 时间更快，因为任何较低的复杂度都不足以查看 the_set 中的所有数字。
在一组大小为 n 的六位数字中，是否有一种算法可以识别该组中相差一个数字的数字，而无需直接将每个元素与其他元素进行比较？是否可以在不到 O(n!) 的时间内完成此操作？
例如，在下面的一组数字中：
789000 889000 543200 125894 156795 146795
789000和889000相差一位数。 156795 和 146795 也相差一位数。算法需要识别这些数字。
直截了当的解决方案是渐近最优的：
def elements_one_apart(the_set):
result = set() # create a new set
for x in the_set:
for y in numbers_different_from_x_by_one_digit(x):
if y in the_set:
result.add(x)
break # skip to the next value of x
return result
外循环迭代the_set的n个元素，内循环最多迭代y的6 * 9 = 54个值。所以内层循环的迭代次数为O(n).
如果使用 hash-set data structure，in 和 add 操作各需要 O(1) 时间。所以总的时间复杂度是O(n)。如果输入不是hash-set，那么可以在O(n)时间内转换成hash-set，所以算法还是O(n)
没有解决方案可能比 O(n) 时间更快，因为任何较低的复杂度都不足以查看 the_set 中的所有数字。