Python|寻求两个数对之间的最大乘积

问题描述

两个数对 (a, b) 和 (c, d) 之间的 乘积差 定义为 (a * b) - (c * d) 。

例如,(5, 6) 和 (2, 7) 之间的乘积差是 (5 * 6) - (2 * 7) = 16 。

给你一个整数数组 nums ,选出四个 不同的 下标 w、x、y 和 z ,使数对 (nums[w], nums[x]) 和 (nums[y], nums[z]) 之间的 乘积差 取到 最大值 。

返回以这种方式取得的乘积差中的 最大值 。

输入:nums = [5,6,2,7,4]

输出:34

解释:可以选出下标为 1 和 3 的元素构成第一个数对 (6, 7) 以及下标 2 和 4 构成第二个数对 (2, 4)

乘积差是 (6 * 7) - (2 * 4) = 34

解决方案

本题的基本思路就是贪心算法,这题我们只需要找出nums中的最大最小的两个数组值,那么就是找出nums中最大的两个元素的乘积和最小的两个元素的乘积,相减即可。但是重要的是正确找到元素的下标,每一个元素的下标一定互不相同。然后就是个人的解法,先从小到大排序,然后用max函数和min函数得到两个乘积,最后相减就得到了结果。个人代码很短,但是所消耗的时间较长,时间复杂度高。对于内置函数max(),该函数的功能为取出传入的多个参数的最大值,以及传入的可迭代对象元素的最大值,只是该题中没有涉及。

结语

本题目的难度不大,做法也很多,我用到的是贪心算法,就是遍历数后去找两个乘积。

作者:沈志坚

实习编辑:王晓姣

稿件来源:深度学习与文旅应用实验室(DLETA)

(0)

相关推荐