4.8python如何求解最小三元组距离

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了4.8python如何求解最小三元组距离，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3412字，纯文字阅读大概需要5分钟。

内容图文

题目描述：

已知三个升序整数数组 a[l], b[m], c[n]，请在三个数组中各找出一个元素，使得组成的三元组距离最小。三元组距离的定义是：假设 a[i], b[j], c[k] 是一个三元组，那么距离为：
Distance=max（| a[i] - b[j] |，| a[i] - c[k]|，| b[j] - c[k] |）。
设计一个求最小三元组距离的最优算法。

方法：
最简单的方法是找出所有可能的组合，从所有可能的组合中找出最小距离，但是效率低下。
通过分析发现，当 a<= b <= c 时，此时它们的距离肯定为 D = c-a，此时就没有必要计算 b-a，c-b了。

1. 蛮力法
2. 最小距离法
3. 数学运算法

1.蛮力法
分别遍历三个数组中的元素，对遍历到的元素分别求出它们的距离，然后按照距离的定义得出最小的距离。

代码实现：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time    : 2020/1/29 19:34
# @Author  : buu
# @Software: PyCharm
# @Blog    ：https://blog.csdn.net/weixin_44321080
def maxx(a, b, c):
    maxs = b if b > a else a
    maxs = c if c > maxs else maxs
    return maxs


def miDistance(a, b, c):
    aLen = len(a)
    bLen = len(b)
    cLen = len(c)
    minDist = maxx(abs(a[0] - b[0]), abs(a[0] - c[0]), abs(b[0] - c[0]))
    i = 0
    while i < aLen:
        j = 0
        while j < bLen:
            k = 0
            while k < cLen:
                dist = maxx(abs(a[i] - b[j]), abs(a[i] - c[k]), abs(b[j] - c[k]))
                if dist < minDist:
                    minDist = dist
                k += 1
            j += 1
        i += 1
    return minDist


if __name__ == '__main__':
    a = [3, 4, 5, 7, 15]
    b = [10, 12, 14, 16, 17]
    c = [20, 21, 23, 24, 37, 30]
    print('min dist:', miDistance(a, b, c))

结果：

算法性能分析：

时间复杂度为O(lmn)；
这种方法没有用到数组升序的特点。

2.最小距离法
假设当前遍历到这三个数组中的元素分别为 a_i，b_i，c_i，且 a_i <= b_i <= c_i，此时它们的距离肯定为 D_i = c_i - a_i；那么接下来分如下三种情况讨论：
(1) 接下来如果求 a_i，b_i，c_i+1 的距离，由于 c_i+1 >= c_i ，此时它们三元组的距离必为D_i+1 = c_i+1 - a_i，显然 D_i+1 >= D_i ,所以 D_i+1 不可能为最小距离。
(2) 接下来如果求 a_i，b_i+1，c_i+ 的距离，由于 b_i <= b_i+1 ，

• 若 b_i+1 <= c_i ，此时它们三元组的距离仍为 D_i = c_i - a_i；
• 若 b_i+1 > c_i , 此时它们三元组的距离必为D_i+1 = b_i+1 - a_i，显然 D_i+1 >= D_i ,所以 D_i+1 不可能为最小距离。

(3) 如果接下来求 a_i+1，b_i，c_i 的距离，若 D_i = | c_i - a_i | < c_i - a_i+1 ，此时它们的距离为 max（c_i - a_i+1，c_i - b_i），显然 D_i+1 < D_i ，所以 D_i+1 有可能时最小距离。

综上，在求最小距离的时候只需要考虑第三种情况即可。具体实现思路：
从三个数组的第一个元素开始，首先求出它们的距离 minDist ，接着找出这三个数中最小数所在的数组，只对这个数组的下标往后移动一个位置，接着求三个数组中当前遍历元素的距离，如果比 minDist 小，则把当前距离赋值给 minDist ，依此类推，直到遍历完其中一个数组为止。

代码实现：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time    : 2020/1/29 19:49
# @Author  : buu
# @Software: PyCharm
# @Blog    ：https://blog.csdn.net/weixin_44321080
def maxx(a, b, c):
    maxs = b if b > a else a
    maxs = c if c > maxs else maxs
    return maxs


def minn(a, b, c):
    mins = a if a < b else b
    mins = c if c < mins else mins
    return mins


def minDistance(a, b, c):
    aLen = len(a)
    bLen = len(b)
    cLen = len(c)
    minDist = 2 ** 32
    minElem = 0
    i, j, k = 0, 0, 0
    while True:
        curDist = maxx(abs(a[i] - b[j]), abs(a[i] - c[k]), abs(b[j] - c[k]))
        if curDist < minDist:
            minDist = curDist
        minElem = minn(a[i], b[j], c[k])
        if minElem == a[i]:
            i += 1
            if i >= aLen:
                break
        elif minElem == b[j]:
            j += 1
            if j >= bLen:
                break
        else:
            k += 1
            if k >= cLen:
                break
    return minDist


if __name__ == '__main__':
    a = [3, 4, 5, 7, 15]
    b = [10, 12, 14, 16, 17]
    c = [20, 21, 23, 24, 37, 30]
    print('min dist2:', minDistance(a, b, c))

结果：

算法性能分析：
此方法最多只需要对三个数组分别遍历一遍，所以时间复杂度为O(l+m+n)；

end

• 点赞
• 收藏
• 分享
• • 文章举报

内容总结

以上是互联网集市为您收集整理的4.8python如何求解最小三元组距离全部内容，希望文章能够帮你解决4.8python如何求解最小三元组距离所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端