【语法】
一、隐蔽陷阱
1 到 n 的流水号少了一个要找出来:逐个比对要先排序;两两异或的思路又撞上 Lua 5.1 没有位运算符的墙。
二、底层原理
高斯求和:n(n+1)/2 是理论总和,实和与理论值之差就是缺的那个数。一遍累加即可,空间常数级;Lua 数值是双精度,n 在 2 的 53 次方以内求和依旧精确。
三、正确代码
基础写法(求和作差):
local function missingSum(a)
local n = #a + 1
local total = n * (n + 1) / 2
local s = 0
for _, v in ipairs(a) do s = s + v end
return total - s
end
进阶写法(原地交换归位):
local function missingSwap(a)
for i = 1, #a do
while a[i] <= #a and a[a[i]] ~= a[i] do
local j = a[i]
a[i], a[j] = a[j], a[i]
end
end
for i = 1, #a do
if a[i] ~= i then return i end
end
return #a + 1
end
local p = getplayerbyname("miss01")
sendmsg(p, 1, missingSum({1, 2, 4, 5}) .. "/" .. missingSwap({3, 1, 4, 5}))
四、引擎验证
{1,2,4,5} 缺 3,求和版返回 3;{3,1,4,5} 乱序缺 2,归位版交换到位后返回 2;一个不缺时返回 n+1。
五、FAQ
问:求和会溢出吗?
答:双精度整数在 2 的 53 次方以内都精确,流水号规模远够不到。
问:缺多个数怎么办?
答:求和只能定位一个,多个缺失改用标记表逐个排查。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏功能】 拆一行代码: 一个格子的数字、周围没翻开的格子数、周围已插的旗数——三者相等的那一刻,剩余未开格全是雷。扫雷的…
【游戏功能】 夺旗为什么比杀人有意思?因为旗子是"带得走的胜利":拔旗只要一瞬,背回家才是全程——从拔到旗那一刻起,背旗的人…
【游戏功能】 空投为什么让人疯狂?箱子还没落地,地图上八个方向的人已经在往落点狂奔——空投的魔力不在箱子本身,在于它把"好东…
【游戏功能】 棋牌室里流传一句老话:新手看自己的棋,高手看对手的棋。五子棋 AI 的写法恰好是这句话的注脚——只会给自己找连…
【游戏功能】 拆一行代码: 把朝向原地翻转一百八十度——回马枪的全部机关就这一行。佯装败退的人在追兵眼皮底下突然回头,枪尖从…
【游戏功能】 擂台上演过一幕静悄悄的事故:一个法师对着两人小队放大招,闪电劈在甲身上,乙毫发无伤地站在半步之外看戏——事后他…