Sweet Snippet 之 计算逆序数
Sweet Snippet 之 计算逆序数
用户2615200
发布于 2021-12-24 18:20:31
发布于 2021-12-24 18:20:31
本文简单介绍了几种计算逆序数的实现方法
简介
所谓逆序数,是指一个排列中所有逆序对的总数,而所谓逆序对,则是指排列中前后位置和大小顺序相反的数对,举个简单的例子:
\{\ 1, 4, 2, 3 \ \}
上面的排列中,有下面两个逆序对:
<4, 2>\ <4, 3>
所以该排列的逆序数为 2
实现
- 朴素的实现很简明,我们遍历排列中所有的数对,检查是否形成逆序关系即可,示例代码如下(Lua):
function inverse_number(seq)
local inv_num = 0
for i = 1, #seq - 1 do
for j = i + 1, #seq do
if seq[i] > seq[j] then
inv_num = inv_num + 1
end
end
end
return inv_num
end- 上面的方法虽然简明,但是时间复杂度相对较高 O(n^2) ,这里我们假设排列中元素种类很少(譬如只有 1, 2, 3, 4 ,那么更有效率的一种实现方法就是依次遍历排列元素,对于每一个遍历到的元素而言,该元素之前所有比他(该元素)大的元素,与该元素便形成了一个逆序对(即逆序数增一),依此我们便可以累加计算出排列的逆序数(Lua):
-- assume seq contains "1, 2, 3, 4" only
function inverse_number(seq)
local inv_num = 0
local count_buffer = { 0, 0, 0, 0 }
for i = 1, #seq do
if seq[i] == 1 then
inv_num = inv_num + count_buffer[2] + count_buffer[3] + count_buffer[4]
count_buffer[1] = count_buffer[1] + 1
elseif seq[i] == 2 then
inv_num = inv_num + count_buffer[3] + count_buffer[4]
count_buffer[2] = count_buffer[2] + 1
elseif seq[i] == 3 then
inv_num = inv_num + count_buffer[4]
count_buffer[3] = count_buffer[3] + 1
else
count_buffer[4] = count_buffer[4] + 1
end
end
return inv_num
end- 上面代码的时间复杂度虽然比较高效 O(n) ,但是通用性不高(限制了排列元素种类),我们可以简单扩展一下(Lua):
function inverse_number(seq)
local inv_num = 0
local count_buffer = {}
for i = 1, #seq do
for k, v in pairs(count_buffer) do
if k > seq[i] then
inv_num = inv_num + v
end
end
count_buffer[seq[i]] = (count_buffer[seq[i]] or 0) + 1
end
return inv_num
end- 实际上而言,上面实现的时间复杂度也是 O(n^2),但在元素种类受限的排列中,使用该实现来求取逆序数的速度仍是非常快的,另外的,我们还可以借用树状数组来进一步加速,有兴趣的朋友可以继续看看更多资料里的内容.
更多资料
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-12-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录