我刚刚完成了这个练习题:
给定一个整数列表,返回任意三个整数相乘所得的最大乘积。 例如,如果列表是 [-10, -10, 5, 2],我们应该返回 500,因为这是 -10 * -10 * 5。
我编写了以下代码,它似乎可以工作,但我觉得它可以更简单。有什么想法吗?
def maxProduct(lst):
combo = []
for i in range(0,len(lst)):
for j in range(0,len(lst)):
for k in range(0,len(lst)):
if i != j and j != k and i != k:
x = sorted([lst[i]] + [lst[j]] + [lst[k]])
if x not in combo:
combo.append(x)
final = []
for i in combo:
result = 1
for j in i:
result = result * j
final.append(result)
return max(final)
采用类似的“强力”方法,您可以使用一些内置函数使其成为单行代码(以及一些导入):
from itertools import combinations
from functools import reduce
from operator import mul
result = max(reduce(mul, p, 1) for p in combinations(arr, 3))
考虑到列表是整数,只有两种非退化的可能性:
对列表进行排序。
return max( values[-1] * values[-2] * values[-3],
values[-1] * values[ 0] * values[ 1])
将
x = sorted([lst[i]] + [lst[j]] + [lst[k]])
更改为 x = sorted([lst[i], lst[j], lst[k]])
这是一种通用但非常快速的方法(
O(n)
对于小k
)执行此操作(< 6ms for 100K elements and k=3
)。
它是通用,因为如果您选择的话,您可以查找任何
k>0
值(偶数或奇数)的最大乘积,而不仅仅是k=3
。
这个想法是寻找顶部
k
和底部 k
值(hi
,分别为 lo
)。我们不使用排序 (O(n log n)
),而是使用 heapq
(O(n)
,使用了两次)来查找 hi
和 lo
。
通常
hi
将具有最大的正值,而 lo
将具有最大的负值,但如果 hi
中存在负值或 lo
中存在正值,则它会起作用。然后我们在 k
列表 2k
中寻找 hi + lo
组合。
from itertools import combinations
from functools import reduce
from operator import mul
import heapq
def prod(lst):
return reduce(mul, lst, 1)
def find_max_prod(lst, k):
hi = heapq.nlargest(k, lst)
lo = heapq.nsmallest(min(k, len(lst) - len(pos)), lst)
return max((prod(vals), vals) for vals in combinations(hi + lo, r=k))
这还会返回产品及其贡献值(用于检查):
>>> find_max_prod([-10, -10, 5, 2], k=3)
(500, (-10, -10, 5))
>>> find_max_prod([-10, -10, 7, 3, 1, 20, -30, 5, 2], k=3)
(6000, (-30, -10, 20))
>>> find_max_prod([-10, -10, 7, 3, 1, 20, -30, 5, 2], k=4)
(42000, (-30, -10, 20, 7))
n = 100_000
lst = np.random.randint(-20, 20, size=n).tolist()
%timeit find_max_prod(lst, 3)
# 5.7 ms ± 1.15 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
如果没有正数(或没有负数),它就有效:
>>> find_max_prod([-1,-2,-1,-5], 3)
(-2, (-1, -1, -2))
>>> find_max_prod([5,6,7,8], 3)
(336, (8, 7, 6))
它也适用于浮动:
>>> lst = np.random.normal(size=n).tolist()
... lst[:4]
[-1.2645437227178908,
0.04542859270503795,
-0.17997935575118532,
-0.03485546753207921]
>>> find_max_prod(lst, 3)
(72.00185172194192,
(-4.159094140171658, -4.145875048073711, 4.175694390863968))
您可以将问题分解为子问题并使用它:
highest_product_of_3: 迄今为止任何三个数字的最高乘积。
highest_product_of_2: 迄今为止任何两个数字的最高乘积。
lowest_product_of_2: 迄今为止任何两个数字的最低乘积(如果我们有两个大负数,可能会很有用)。
最高:迄今为止看到的最高数字。
最低:迄今为止看到的最低数字。
def highest_product_of_3(list_of_ints):
if len(list_of_ints) < 3:
raise ValueError('Less than 3 items!')
# Initialize highest and lowest based on the first two elements
highest = max(list_of_ints[0], list_of_ints[1])
lowest = min(list_of_ints[0], list_of_ints[1])
# Initialize highest and lowest products of two
highest_product_of_2 = list_of_ints[0] * list_of_ints[1]
lowest_product_of_2 = list_of_ints[0] * list_of_ints[1]
# Initialize the highest product of three
highest_product_of_3 = list_of_ints[0] * list_of_ints[1] * list_of_ints[2]
# Iterate through the list starting from the third element
for i in range(2, len(list_of_ints)):
current = list_of_ints[i]
# Update highest_product_of_3
highest_product_of_3 = max(
highest_product_of_3,
current * highest_product_of_2,
current * lowest_product_of_2
)
# Update highest_product_of_2
highest_product_of_2 = max(
highest_product_of_2,
current * highest,
current * lowest
)
# Update lowest_product_of_2
lowest_product_of_2 = min(
lowest_product_of_2,
current * highest,
current * lowest
)
# Update highest
highest = max(highest, current)
# Update lowest
lowest = min(lowest, current)
return highest_product_of_3
简单朴素的实现 (O(n3)):
import itertools
def max_product_of_three(values):
return max(
x * y * z
for x, y, z in itertools.combinations(values, 3)
)
您可以通过首先对值进行排序来改进这一点。
编辑:这是一个性能更高的 (O(n)) 解决方案
import heapq
def max_product_of_three(values):
x, y, z = heapq.nlargest(3, values)
a, b = heapq.nsmallest(2, values)
return max(
x * a * b,
x * y * z
)