提问人：BlackPearl 提问时间：10/12/2022 最后编辑：VLAZBlackPearl 更新时间：10/12/2022 访问量：65
如何在二维数组中找到唯一数
How to find unique number in 2D Array
问：
我有一个二维数组，外部数组的索引表示 StateID，内部数组中的整数表示 StoreID。
StoreStateList = [[1,2],[1,2,3],[1,3,7,9],[1,8,12],[7,9,12]]
我正在尝试找到一个拥有其他州没有的商店的州。例如，状态 3 和 StoreID 为 8。
我目前的实现由 4 个嵌套循环组成，看起来效率低下。有谁知道如何使功能更有效率？
function findUniqueStore(StoreRegionList)
for state in range(len(StoreRegionList):
state_count = 0
for store in StoreStateList[state]:
// check if the store in the state occurs in any other state
for state_inner in range(len(StoreRegionList)):
for store_inner in StoreStateList[state_inner]:
if store == store_inner:
state_count += 1
if state_count == 1:
return state
答：
1赞
pasthec
10/12/2022
#1
您可以使用两个 python 集来存储潜在的唯一元素和访问的元素。在前两个 for 循环中，检查当前元素是否已经被看到，如果没有，请将其添加到潜在的唯一元素中，或者如果它仍然存在，则将其从唯一元素中删除：
def findUniqueStore(StoreRegionList):
visitedNumbers = set()
uniqueNumbers = set()
for state in range(len(StoreRegionList):
for store in StoreStateList[state]:
// check if the store in the state occurs in any other state
if store not in visitedNumbers:
uniqueNumbers.add(store)
visitedNumbers.add(store)
elif store in uniqueNumbers:
uniqueNumbers.remove(store)
if len(uniqueNumbers)>0:
return next(iter(uniqueNumbers))
这给出了一个 nlog（n） 解决方案，其中 n 是元素的总数，而不是 n² 表示您的元素。
编辑：我没有意识到您没有明确要求 python 解决方案，但关键是您可以使用每种语言的标准库中的集合，这些集合通常使用平衡的二叉树实现，以支持在 log（n） 时间内插入、检查和删除元素。
评论
0赞
BlackPearl
10/12/2022
这几乎正是我所需要的。但是，我需要返回状态号，而不是商店号。我尝试使用状态变量调整您的代码，但无法使其工作（还）。你有返回状态的解决方案吗？多谢！
0赞
pasthec
10/12/2022
您可以使用 python 字典（即哈希表）而不是 set 来存储与潜在唯一编号（key=store、value=state）关联的状态值。检查字典中的键与检查元素是否在集合中的语法相同。最后返回.uniqueNumbersuniqueNumbers[next(iter(uniqueNumbers))]
0赞
CJK
10/13/2022
“您可以使用每种语言的标准库中的集合”呃......真？！
0赞
pasthec
10/13/2022
@CJK 当然，每一个可能都有些夸大其词，但它肯定存在于大多数编程语言的标准库中，只要你使用一些旨在做算法的东西，并且稍微流行一点，第一个谷歌结果就会告诉你如何声明集合。
0赞
CJK
10/19/2022
你已经回溯了每一个，并添加了稍微流行的警告，欢迎你加入这两个，但你仍然会兜售一个令人震惊的谎言。有 C、汇编、Fortran、Lisp（以及许多函数式编程语言）、Perl、大多数 shell 脚本语言、Awk、AppleScript、XSLT、SQL（尽管它提供 Set 操作）、PHP、Logo（仍然很受欢迎，尤其是在学校）、Visual Basic（我记得最后一次）、......侧面相关查询：有没有不该做算法的语言？
上一个：使用 2D 阵列查找孤立的城市
评论
Python