正整数数组中 k 个整数的最小乘积

2025年3月17日 | 阅读 3 分钟

让我们来理解这个问题:我们需要在一个包含 n 个正整数的数组中找到 k 个整数的乘积,其中 k<=n。

让我们举个例子

如果数组是:[10,5,4,7,8,1,2],k 值为 2,

我们需要找到通过相乘数组中的任意两个数字所能得到的最小可能乘积。

我们知道,只有当我们将数组中的最小几个值相乘时,才能得到最小的乘积。

所以,我们首先需要找出数组中最小的 k 个元素并相乘。

与其单独找出它们,不如对数组进行排序,然后相乘前 k 个数字。

当我们对上述数组进行排序时,它变成:[1,2,4,5,7,8,10]

k 值为 2,所以我们相乘前 2 个数字,它们是 1 和 2。

乘积 = 1*2 = 2。

如果 k 值为 5,则最小可能的乘积是 1*2*4*5*7 = 280。

所以,现在我们需要实现一个代码,该代码接受数组大小和数组元素作为输入,然后询问用户输入 k 值,接着我们需要对给定的数组进行排序。最后,我们将相乘前 k 个值以获得所需的结果。

那么,让我们来实现代码。

代码

输出

Minimum product of k integers in an array of positive integers

说明

首先,在代码中,我们需要获取数组大小和数组元素的输入。

这部分代码将获取输入数组的大小,并将数组元素存储在一个名为 vec 的数组中。

接下来,我们需要对给定的输入数组进行排序,这可以通过使用

接下来,我们提示用户输入 k 的大小,然后我们需要打印出从数组中任意 k 个元素中可能得到的最小乘积。

因此,为了获得最小乘积,我们相乘前 k 个值,所以我们需要执行以下操作。

Val 初始化为 1,然后我们将 val 与数组的前 k 个元素相乘。

我们将得到数组中 k 个元素可能得到的最小乘积。

这里,我们需要处理 k>n 的情况;当这种情况发生时,表示请求错误,所以当用户给出的 k 值使得 k>n 时,我们将打印“Cannot multiply k cannot be greater than n”(无法相乘,k 不能大于 n)。

这是通过

我们通过上面的 if 条件(k>n)打印错误消息并退出。

最后,我们将打印出相乘 k 个元素后得到的值,我们还将打印出产生该乘积的值的元素。

即,我们还打印出数组的前 k 个元素。

使用上述代码,将打印出 vector 的 val 和前 k 个元素。

让我们也看看当我们给出 k>n 时的情况。

Minimum product of k integers in an array of positive integers

在上面的输出中,我们可以看到 n 是 5,k 值为 8;这里 k>n,所以我们无法操作,因此我们将打印“Cannot multiply k cannot be greater than n”(无法相乘,k 不能大于 n)。