在Lua中从两个向量中取出公共元素

我有两个向量,假设v1 = (a,b,c,d,e)v2 = (e,h,t,b,w),我想获取第三个向量,其中包含v1v2的共同元素,即v3 = (e,b)

我已经看到这个问题被问到了c++中,但我在Lua中找不到它。

点赞
用户1009479
用户1009479

我假设你说的向量是指v1v2都是类似数组的表格,像这样:

local v1 = {1,2,4,8,16}
local v2 = {2,3,4,5}

然后你可以这样做:

local v3 = {}

for k1,v1 in pairs(v1) do
    for k2,v2 in pairs(v2) do
        if v1 == v2 then
            v3[#v3 + 1] = v1
        end
    end
end
2013-08-07 15:59:35
用户107090
用户107090

与Yu Hao的解决方案不同,下面的代码在线性时间内运行,但是除非您可以使用v3而不是坚持使用v4,否则它确实需要额外的内存。尽管如此,时间差可能只有在大型输入向量中才会注意到。

local v1={1,2,4,8,16}
local v2={2,3,4,5}
local v3={}
for k,v in ipairs(v1) do v3[v]=false end
for k,v in ipairs(v2) do if v3[v]==false then v3[v]=true end end
for k,v in  pairs(v3) do if v3[k]==false then v3[k]=nil end end
local v4={}
local n=0
for k,v in  pairs(v3) do n=n+1; v4[n]=k end
for k,v in ipairs(v4) do print(k,v) end
2013-08-07 16:21:34
用户501459
用户501459

你可以通过对 v1 进行一次遍历来构建查找表,然后通过对 v2 进行一次遍历来查找相同的值并将它们添加到输出列表中:

function findcommon(a1, a2)
    local in_a1 = {} -- 用于 a1 值的查找表
    for k,v in pairs(a1) do in_a1[v] = true end

    local common = {}
    local n = 0
    for k,v in pairs(a2) do
        if in_a1[v] then
            in_a1[v] = false
            n = n + 1
            common[n] = v
        end
    end

    return common
end

以你的例子为例:

v1 = {'a','b','c','d','e'}
v2 = {'e','h','t','b','w'}
common = findcommon(v1,v2)

print('('..table.concat(common,',')..')')  --> (e,b)
2013-08-07 18:17:02
用户847349
用户847349

对于想要计算交集的大向量(数组/集合)的情况,在此提供一种未经测量的早期优化的方案

local v1 = {1,2,4,8,16}
local v2 = {2,3,4,5}

local function intersect(t1,t2)

        local function make_lookup(t)
            local res={}
            for _,v in ipairs(t) do
                res[v]=true
            end
            return res
        end

        local smaller,larger
        if (#t1>#t2) then
            larger=t1
            smaller=t2
        else
            larger=t2
            smaller=t1
        end

        local lookup=make_lookup(smaller)

        local res={}
        for _,v in ipairs(larger) do
            if lookup[v] then
                res[#res+1]=v
            end
        end
        return res
end

local v1v2_intersected=intersect(v1,v2)

内部查找表由其中较小的数组表构成。在“生产”中,您也许还想要检查你所处理的输入值是否正确。

2013-08-08 12:49:47