Sweet Snippet 之 计算 MaxSortedDistance
source link: https://blog.csdn.net/tkokof1/article/details/134362538
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
本文简述了 计算 MaxSortedDistance 的一些方法
所谓 MaxSortedDistance,是指一个无序数组经过排序后相邻元素的最大差值.
举个例子,如果给定无序数组:
1000 , 13 , 1 , 7 , 5 , 3 , 100 1000, 13, 1, 7, 5, 3, 100 1000,13,1,7,5,3,100
那么该数组的 MaxSortedDistance 即为 900,因为该数组经过排序后为:
1 , 3 , 5 , 7 , 13 , 100 , 1000 1, 3, 5, 7, 13, 100, 1000 1,3,5,7,13,100,1000
其中相邻元素最大的差值为:
1000 − 100 = 900 1000 - 100 = 900 1000−100=900
最简单直白的实现方法自然是直接给数组排序,然后计算最大的相邻元素差值即可:
function get_max_sorted_distance_sort(num_table)
table.sort(num_table)
local max_sort_distance = 0
for i = 2, #num_table do
if num_table[i] - num_table[i - 1] > max_sort_distance then
max_sort_distance = num_table[i] - num_table[i - 1]
end
end
return max_sort_distance
end
代码简单直白,通俗易懂.
但是排序数组的时间复杂度比较高,有可能进一步降低吗?
一种方式便是借鉴 计数排序 的算法思路来给数组"排序":
function get_max_sorted_distance_count(num_table)
local num = #num_table
if num > 1 then
local min = num_table[1]
local max = min
for i = 2, num do
local val = num_table[i]
if val < min then
min = val
elseif val > max then
max = val
end
end
local num_buffer = {}
for i = 1, max - min + 1 do
num_buffer[i] = 0
end
for i = 1, num do
-- no need to '+= 1' here(just need '=1')
num_buffer[num_table[i] - min + 1] = 1
end
local max_sort_distance = 0
local cur_sort_distance = 0
for i = 2, max - min + 1 do
if num_buffer[i - 1] == 0 and num_buffer[i] ~= 0 then
if cur_sort_distance + 1 > max_sort_distance then
max_sort_distance = cur_sort_distance + 1
end
cur_sort_distance = 0
elseif num_buffer[i - 1] == 0 and num_buffer[i] == 0 then
cur_sort_distance = cur_sort_distance + 1
elseif num_buffer[i - 1] ~= 0 and num_buffer[i] == 0 then
cur_sort_distance = 1
elseif num_buffer[i - 1] ~= 0 and num_buffer[i] ~= 0 then
-- no need to set here
--cur_sort_distance = 0
end
end
return max_sort_distance
end
return 0
end
但是计数排序的算法思路至少有两个问题:
- 数组元素相差较大时,空间消耗较大
- 仅适用于整形类型数组
对于此,我们可以采用桶排序的算法思路来解决:
function get_max_sorted_distance_bucket(num_table)
local num = #num_table
if num > 1 then
local min = num_table[1]
local max = min
for i = 2, num do
local val = num_table[i]
if val < min then
min = val
elseif val > max then
max = val
end
end
local bucket_buffer = {}
local bucket_range = (max - min) / (num - 1)
-- check nearly zero here
local epsilon = 1e-5
if bucket_range <= epsilon then
return 0
end
for i = 1, num do
bucket_buffer[i] = {}
end
for i = 1, num do
local index_raw = (num_table[i] - min) / bucket_range
local index = math.floor(index_raw + 0.5) + 1
if bucket_buffer[index] then
if bucket_buffer[index].min then
if num_table[i] < bucket_buffer[index].min then
bucket_buffer[index].min = num_table[i]
end
else
bucket_buffer[index].min = num_table[i]
end
if bucket_buffer[index].max then
if num_table[i] > bucket_buffer[index].max then
bucket_buffer[index].max = num_table[i]
end
else
bucket_buffer[index].max = num_table[i]
end
else
print("[get_max_sort_distance_bucket]out of bucket size error occur ...")
end
end
local max_sort_distance = 0
local pre_bucket_index = 0
for i = 1, num do
-- seems no need to check min and max in same bucket
--[[
if bucket_buffer[i].min and bucket_buffer[i].max then
local bucket_distance = bucket_buffer[i].max - bucket_buffer[i].min
if bucket_distance > max_sort_distance then
max_sort_distance = bucket_distance
end
end
--]]
if pre_bucket_index > 0 then
if bucket_buffer[pre_bucket_index].max and bucket_buffer[i].min then
local bucket_distance = bucket_buffer[i].min - bucket_buffer[pre_bucket_index].max
if bucket_distance > max_sort_distance then
max_sort_distance = bucket_distance
end
end
end
if bucket_buffer[i].max then
pre_bucket_index = i
end
end
return max_sort_distance
end
return 0
end
测试代码:
local t = { 1000, 13, 1, 7, 5, 3, 100 }
print(get_max_sorted_distance_count(t))
print(get_max_sorted_distance_bucket(t))
print(get_max_sorted_distance_sort(t))
很久没有动手写博文了,原因能"编"出来很多,大抵都是些老生长谈的东西,不赘述了,今天也仅是兴盛所致写了一篇,希望以后能多写一些了,是为记.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK