lua - 我们如何以最小的时间复杂度检查 lua 表中是否存在相似的元素

Question

如果存在 N 个整数的表，如何检查元素是否重复（如果存在）它显示表具有重复元素的消息，如果要以最小时间复杂度实现这一点

标签： lualua-table

Answer 1

哈希表是要走的路（即普通的Lua表）。只需遍历每个整数并将其作为键放入表中，但首先检查键是否已存在。如果是这样，那么你有一个重复值。所以像：

values = { 1, 2, 3, 4, 5, 1 } -- input values

local htab = {}
for _, v in ipairs(values) do
  if htab[v] then print('duplicate value: ' .. v)
  else htab[v] = true end
end

对于小整数值，该表将使用数组，因此访问时间为 O(1)。对于较大且因此较稀疏的值，这些值将位于表的哈希表部分，也可以假设为 O(1)。因为你有 N 个值要插入，所以这是 O(N)。

应该不可能比 O(N) 更快，因为您必须至少访问列表中的每个值一次。