给定长度为 n 的整数数组 nums
,其中 n > 1,返回输出数组 output
,其中 output[i]
等于 nums
中除 nums[i]
之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。
进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)
解题思路:
如果能用除法的话,问题会变得很简单,只需要将所有整数的乘积求出,然后除以当前数,即为除了当前数以外的所有数字的乘积(不考虑有0的情况)。在不能使用除法的情况下,可以通过减法来实现除法,但是当数组中元素个数很大的时候,减法的次数会变得非常之多,时间复杂度也会远远超过O(n)。在这种情况下,考虑用二进制移位和加减的方式来实现除法,时间复杂度为降为O(n)。
另外,还要考虑数组中有0的情况,如果0的个数不止一个的话,则得到的所有输出全为0;
如果0的个数只有一个的话,那么除了