題目描述

已知三個升序整數(shù)數(shù)組a[l], b[m]和c[n]。請在三個數(shù)組中各找一個元素，是的組成的三元組距離最小。三元組的距離定義是：假設(shè)a[i]、b[j]和c[k]是一個三元組，那么距離為:

Distance = max(|a[ I ] – b[ j ]|, |a[ I ] – c[ k ]|, |b[ j ] – c[ k ]|)

請設(shè)計一個求最小三元組距離的最優(yōu)算法，并分析時間復(fù)雜度。

解題思路

保持三個下標索引 i,j,k，找出a[i],b[j],c[k]里最小的元素。如果a[i]最小, 則下一次循環(huán) i=i+1, 其他兩個索引不變。如果b[j]最小, 則下一次循環(huán) j=j+1, 其他兩個索引不變。如果c[k]最小, 則下一次循環(huán) k=k+1, 其他兩個索引不變。如此循環(huán)，直至最小的數(shù)對應(yīng)的下標到達該數(shù)組尾部。記錄最小距離。

時間復(fù)雜度：O(l+m+m) （每次循環(huán)總有一個下標走了一步）。

代碼實現(xiàn)

#方法二 def mins(a,b,c):mins = a if a < b else bmins = mins if mins < c else creturn minsdef maxs(a,b,c):maxs = b if a < b else amaxs = c if maxs < c else maxsreturn maxsdef minDistance(a,b,c):aLen = len(a)bLen = len(b)cLen = len(c)curDist = 0minsd = 0minDist = 2 ** 32i = 0 #數(shù)組a的下標j = 0 #數(shù)組b的下標k = 0 #數(shù)組c的下標while True:curDist = maxs(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))if curDist < minDist:minDist = curDist#找出當前遍歷到三個數(shù)組中最小值minsd = mins(a[i],b[j],c[k])if minsd == a[i]:i += 1if i >= aLen:breakelif minsd == b[j]:j += 1if j >= bLen:breakelse:k += 1if k >= cLen:breakreturn minDistif __name__ == "__main__":a = [3,4,5,7,15]b = [10,12,14,16,17]c = [20,21,23,24,37,30]print("最小距離為："+str(minDistance(a,b,c)))

?

總結(jié)

以上是生活随笔為你收集整理的三元组最小距离的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。