整数数组的每个元素都被数组中所有其他元素的乘积替换 [英] Each element of an integer array is replaced by the product of all the other elements in the array
问题描述
>函数有两个参数 - （i）array（ii）它的大小（n）
>数组的每个元素都将被其他元素的乘积所取代。 />
>例如，如果以下是数组 - {3,2,1}
，该函数将返回以下输出 - {2,3,6}。
>这不是作业问题。我不希望你这样做。我只是想优化我的程序。
>谢谢。
我的尝试：
我附上了我的函数代码。
正如你所看到的，我使用了一个数组[temp]来存储元素的乘积但我必须初始化每个元素为1手动。
>有没有更好的方法呢？
>你能给出一些关于如何改善时间复杂度的提示吗？代码？
void multiply_input（int str []，int n）
{
int temp [25] = {1,1,1,1,1,1,1,1,1 ，1,1,1,1};
for（int i = 0; i< n; i ++）
{
for（int j = 0; j< n; j ++）
{
if（ i！= j）
temp [i] = temp [i] * str [j];
}
}
for（int k = 0; k< n; k ++）
cout<<< ;< temp [k];
对于初始化，请尝试：
尝试：
int temp [ 25 ];
for （ int i = 0 ; i< 24 ; i ++）
{
temp [i] = 1 < /跨度>;
}或者从文件或用户那里读取值。
至于时间复杂度，这是作业（不管你喜不喜欢）所以我不会给你任何代码。
但是......想一想。
做一个遍历整个数组，计算所有值的乘积。
第二次遍历整个数组，用该总数替换每个元素除以单元格的原始值。
引用：您能否提供一些关于如何提高代码时间复杂度的提示？ / blockquote>
由于临时数组，你的代码运行时复杂度为O（n²），内存复杂度为O（2n）。
随着OG的方法（带除法），运行时复杂度为O（n），内存复杂度为O（n）。
因为你唯一用temp做的事情数组正在打印该值，一旦你获得专业版，你就不需要数组了管道，打印它。
你的代码运行时复杂度为O（n²），内存复杂度为O（n）。
如果你真的需要替换值str，它有点复杂，但是带有部分产品的变量就足够了。
有一种方法可以使它不是O（n平方）而是O（2n）并且不需要临时数组。为此，首先计算数组中所有值的乘积。这是通过一个。然后再次遍历数组，每个元素将是产品除以数组中已有的元素。这个工作的原因是，假设我们有一个三元素数组。第1项是第0项和第2项的乘积。为了给它们字母，b = a * c。为了使用该算法，乘积是p = a * b * c，新b是= p / bOld，它是（a * b * c）/ b并且减少到b = a * c。第二次传递使其成为O（2n），并且存储的唯一值是阵列的初始产品。
这种方法的风险是产品溢出的可能性。如果这些值受到限制并且使用了64位产品，那么将降低风险。当然，这也是O（n平方）方法的风险，但每个产品的因子较少。它有一个缺陷是如果一个或多个值为零，结果就会消失。这可能是赋予值的约束之一，即，值必须在1到32K之间或类似的范围内。只是发生32K是RAND_MAX，这是rand（）返回的最大值，因此它是一个方便使用的值。
>Function has two arguments - (i) array (ii) its size (n)
>Each element of the array will be replaced by the product of the other elements .
>For example if the following is the array -{3, 2, 1}
the function would return the following output - {2,3,6}.
>This is not a homework problem . I don't want you to do it . I just want to optimize my program .
>Thank you.
What I have tried:
I have attached the code of my function.
As you can see , I have used an array [temp] to store the product of the elements but I have to initialize every element as 1 manually .
>Is there any better way to do it ?
>Could you give any hints as to how I can improve the time complexity of the code?
void multiply_input(int str[],int n) { int temp[25]={1,1,1,1,1,1,1,1,1,1,1,1,1}; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i!=j) temp[i]=temp[i]*str[j]; } } for(int k=0;k<n;k++) cout<<" "<<temp[k];解决方案For the initialization, try:
Try:
int temp[25]; for (int i = 0; i < 24; i++) { temp[i] = 1; }Or read the values from a file, or the user.
As for the time complexity, this is homework (whether you like it or not) so I'll give you no code.
But ... think about it.
Do one pass through the whole array, to work out the product of all values.
Do a second pass through the whole array, to replace each element with that total divided by the original value of the cell.
Quote:Could you give any hints as to how I can improve the time complexity of the code?
Your code runtime complexity is O(n²) and memory complexity is O(2n) because of temp array.
With the method of OG (with division), the runtime complexity is O(n) and memory complexity is O(n).
Since the only thing you do with temp array is printing the value, you don't need the array, once you got the product, print it.
Your code runtime complexity will be O(n²) and memory complexity will be O(n).
If you really need to replace the values ofstr, it is a little more complicated, but a variable with partial product is enough to do it.
There is one way to make it not be O(n squared) and instead be O(2n) and a temporary array is not required. To do this, first calculate the product of all values in the array. That is pass one. Then step through the array again and each element will be the product divided by the element already in the array. The reason this works is, let's say we have a three element array. Item 1 is the product of items 0 and 2. To give them letters, b = a * c. To use this algorithm, the product is p = a * b * c and the new b is = p / bOld which is ( a * b * c ) / b and that reduces to b = a * c. This second pass makes it O(2n) and the only value stored is the initial product of the array.
The risk to this approach is the possibility the product will overflow. If the values are constrained and a sixty-four bit product is used that will reduce the risk. Of course, that is also a risk with the O(n squared) approach but it has one less factor in each product. One flaw it has is the result goes out the window if one or more values are zero. This can be one of the constraints given to the values though ie., values must range from 1 to 32K or something like that. It just happens that 32K is RAND_MAX, the largest value returned by rand(), so it is a convenient value to use.
这篇关于整数数组的每个元素都被数组中所有其他元素的乘积替换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
