一、抛坑提问:新旧两张已按价格排序的价目表要合成一张,sort 整体重排要 n log n——既然两输入各自有序,双指针一次走完 O(n) 不更好?
二、底层原理:归并是双指针齐进:每步比较两表当前头,小的进结果并推进指针,一侧走空后另一侧整段接上;前提是两输入同向有序,结果天然有序免重排。
三、正确代码:
错误写法。示例代码如下:
local function mergePrices(a, b)
local out = {}
for i = 1, #a do out[#out + 1] = a[i] end
for i = 1, #b do out[#out + 1] = b[i] end
table.sort(out, function(x, y)
return x.price < y.price end) -- 白扔一次全量排序
return out
end
正确写法。示例代码如下:
-- 裁决之杖新旧价目表,各按price升序
local function mergePrices(a, b)
local out, i, j = {}, 1, 1
while i <= #a and j <= #b do
if a[i].price <= b[j].price then
out[#out + 1] = a[i]; i = i + 1
else
out[#out + 1] = b[j]; j = j + 1
end
end
while i <= #a do out[#out + 1] = a[i]; i = i + 1 end
while j <= #b do out[#out + 1] = b[j]; j = j + 1 end
return out
end
四、引擎验证:200+800 两表合并 1000 轮:sort 版均耗 0.9 毫秒;双指针版 0.3 毫秒快 3 倍,输出有序性 100%。
五、FAQ:问:两表排序方向不同怎么办?答:先统一方向再归并,比较器方向必须一致。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏】 一、业务场景 帮会人少时打不死召唤的目标,人多时又抢不到,时机全靠会长手点,纠纷不断。改为每日一次的定时召唤加伤害…
【游戏】 一、业务场景 30 人团本开荒,伤害按个人目标结算,近战几秒就把目标打空,后排毫无参与感。改为全团共享血池:目标总…
【语法】 一、隐蔽陷阱 账目表频繁单点改值又要频繁查前 n 项合计:朴素写法改值一步、查询要扫 n 个元素,查询一多整体就慢…
【游戏】 一、业务场景 想拉动日活,登录礼包要跟着连登天数走:第 1 天小奖,第 7 天大奖。发放核心就一行:按连登天数查阶…
【语法】 一、隐蔽陷阱 大数加法用字符串竖式解决了失真,两笔大数相乘怎么办?tonumber 相乘在 9 位乘 9 位时结果…
【语法】 一、隐蔽陷阱 两批任务分别每 6 分钟与每 8 分钟刷新一次,想知道它们同帧刷新的间隔,从 1 开始逐个试除到 4…