本文最后更新于 451 天前,其中的信息可能已经有所发展或是发生改变。
没时间更新了,放一波伪代码,有空再补吧。
遍历函数:遍历所有点
//traverse(set):遍历set中所有的点,做差
traverse(set):
flag <- set[0].sub(set[1])
for i 0 to (set.size() - 1) by 1 do:
for j i + 1 to set.size() ny 1 do:
if set[i].sub(set[j]) < flag then:
flag <- set[i].sub(set[j])
end
end
return flag
分治函数:作用是进行分治以及递归,将求出的最小的flag带入到合并函数,返回最终的flag。
//merge(set):分治函数
merge(set):
if set.size() > 3 then:
//数量大于3时,使用分治法
middle <- set.size() / 2
//将set切分为leftSet以及rightSet,分别进行递归
leftFlag = merge(leftSet)
rightFlag = merge(rightSet)
//完成递归后筛选出最小值
flag = min{leftFlag, rightSet}
//将最小值传入合并函数
flag = merge(leftSet, rightSet, flag)
else
//数量小于3时,调用蛮力法
flag <- traverse(set);
return flag
合并函数:将leftSet∈(index – flag, index)与rightSet∈(index, index + flag)做差,若有值小于flag,则覆盖flag。
//merge(leftSet, rightSet, flag)
merge(leftSet, rightSet, flag) :
//将index设为中值
newFlag <- flag;
for i (leftSet.size() - 1) to 0 by -1 do:
//筛选出leftSet中属于[index - flag, index]中的值
if leftSet[i].getX() > index - flag:
exit
//for循环遍历rightSet中的每项
for j : rightSet:
//筛选出rightSet中属于[index, index + flag]中的值
if j.getX() < index + flag:
exit
if leftSet[i].sub(j) < newFlag:
newFlag <- leftSet[i].sub(j)
end
end
return newFlag