[LeetCode]238. Product of Array Except Self 将数组中除了自己以外的数字相乘

题目地址:(?)

https://leetcode.com/problems/product-of-array-except-self/

题目描述:

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

题目大意:

提供一个含有 n 个整数( n > 1 )的数组 nums ,返回一个数组 output ,同时 output[ i ] 等于 nums 数组中除了 nums[ i ] 之外的所有元素的乘积。

不使用除法并且在时间空间复杂度为 O(n) 的情况下解决它。

比如说,给你 [1,2,3,4], 返回 [24,12,8,6].

更进一步:

你能用固定的空间复杂度解决这题吗?(注意:输出结果的数组 output 不记做空间复杂度计算时的额外空间)


 

我又没写出来,又想着用直接乘起来的办法。虽然我知道这样肯定过不去,但我想不出更好的办法。

我超时了。

 

我想用只遍历一遍就把它做出来,因为我对大O算法其实还不够理解吧。O(n) 的意思我还是有些迷糊。然后我的想法是将首位对应的元素相乘,放在一个新的数组里。那么这个数组的个数为总数的一半。遍历前一半的时候可以得到这个数组,遍历后一半的时候进行计算。计算时,遍历那个新的数组里的所有元素,但是将那个选中的元素进行修改,改成对称位置的元素值,因为自己不能被乘进去。然后超时了。

两手一摊。查答案。

答案地址:http://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/72952

“(引用)

题解1 – 左右分治

根据题意,有 result[i]=left[i]⋅right[i]result[i] = left[i] \cdot right[i]result[i]=left[i]⋅right[i], 其中 left[i]=∏j=0i−1A[j]left[i] = \prod {j = 0} ^{i – 1} A[j]left[i]=∏j=0i−1A[j], right[i]=∏j=i+1n−1A[j]right[i] = \prod {j = i + 1} ^{n – 1} A[j]right[i]=∏j=i+1n−1A[j]. 即将最后的乘积分为两部分求解,首先求得左半部分的值,然后求得右半部分的值。最后将左右两半部分乘起来即为解。(看不懂,不过看代码可以知道,就是定义两个数组 left 和 right,一个从左边累乘,每一步得到之前元素的乘积,一个从右边累乘,每一步得到后面元素的乘积,最后将左右相乘即可)

算法是正确的,题目略有偏差。

源码分析

一次for循环求出左右部分的连乘积,下标的确定可使用简单例子辅助分析。

复杂度分析

两次for循环,时间复杂度 O(n)O(n)O(n). 使用了左右两半部分辅助空间,空间复杂度 O(2n)O(2n)O(2n).

题解2 – 原地求积

题解1中使用了左右两个辅助数组,但是仔细瞅瞅其实可以发现完全可以在最终返回结果result基础上原地计算左右两半部分的积。

源码分析

计算左半部分的递推式不用改,计算右半部分的乘积时由于会有左半部分值的干扰,故使用temp保存连乘的值。注意temp需要使用long long, 否则会溢出。

复杂度分析

时间复杂度同上,空间复杂度为 O(1)O(1)O(1).

(这里在求右边数组 right 的时候直接简化了算法,不写 right ,而是直接赋值 result 数组,节省了一部分空间)

那么我还是重写了一遍。

写的过程中,我发现我对左右数组的理解不够深刻,就是,左数组赋值时,右边的下标要比左边小,因为随着下标 i 的增大,所得到的左数组的值会越来越大,就意味着它一直在乘以左边走过去的值,那么这个时候左边的下标必然小于右边。所以才会有 left[i] = left [i – 1] * nums[i – 1]; 这句话。

而右数组则正好相反。右数组的第一个赋值的元素不是 nums[nums_size – 1],而是 nums[nums_size – 2],原因是右数组会不断将选中元素右边的数字相乘,那么右边的下标都大于左边,所以赋值语句的左边下标会小。right[nums_size – i – 1] = right[nums_size – i] * nums[nums_size – i];