赞
踩
Given an array of n integers where n > 1, nums
, return an arrayoutput
such thatoutput[i]
is equal to the product of all the elements ofnums
exceptnums[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.)
分析:
1、如果数组中有两个及以上的0,那么结果数组的每一项都为0.
2、如果数组中只有一个0,那么结果数组中,0对应的位置,为数组中其他元素的成绩,其余位置都为0。
3、如果数组中没有0,那么结果数组每一项均为数组所有元素的乘积/当前数组元素。
需要扫描数组两次,算法时间复杂度为O(n):
第一次:计算0的个数,以及非0元素的乘积。
第二次,计算结果数组每一位的元素。
需要两个临时变量: product保存非0元素的乘积,zeroCount计算0元素的个数,空间复杂度为O(1)。
代码如下:
- class Solution {
- public:
- vector<int> productExceptSelf(vector<int>& nums) {
- long int product = 1;
- vector<int> result;
- int length = nums.size();
- int zerocount = 0;
- for (int i=0; i<length; i++)
- {
- if (nums[i] != 0)
- {
- product *= nums[i];
- }else{
- zerocount++;
- }
-
- }
- for (int i=0; i<length; i++)
- {
- if (nums[i] != 0 )
- {
- if (zerocount != 0)
- result.push_back(0);
- else
- result.push_back(product/nums[i]);
- }else{
- if (zerocount==1)
- result.push_back(product);
- else
- result.push_back(0);
-
- }
- }
- return result;
- }
-
- };
好吧,题目中要求不能用除法。上述算法还是用了除法。另一种不用除法的解法如下:
1)分别计算两个数组,left、right,left[i]为nums[i]的左边元素的成绩,right[i]为nums[i]右边元素的乘积。
2)result[i] = left[i] * right[i]
- class Solution {
- public:
- vector<int> productExceptSelf(vector<int>& nums) {
- int count = nums.size();
- vector<int> result(count, 1);
- vector<int> left(count, 1);
- vector<int> right(count, 1);
-
-
- for (int i = 1; i < count; ++i)
- {
- left[i] = left[i-1] * nums[i-1];
- }
- for (int i = count -2; i >= 0; --i)
- {
- right [i]= right[i+1] * nums[i+1];
- }
- for (int i = 0; i < count; ++i)
- {
- result[i] = left[i] * right[i];
- }
- return result;
- }
- };
这样算法的时间复杂度为O(n),但算法空间复杂度也为O(n),不满足空间O(1)的需求.
题目中提到 返回的结果不计空间,所以直接在result中保存left值。 right 值用变量代替,空间优化后的代码如下:
- class Solution {
- public:
- vector<int> productExceptSelf(vector<int>& nums) {
- int count = nums.size();
- vector<int> result(count, 1);
- int right =1;
-
- for (int i = 1; i < count; ++i)
- {
- result[i] = result[i-1] * nums[i-1];
- }
- for (int i = count -2; i >= 0; --i)
- {
- right *= nums[i+1];
- result[i] *= right;
- }
- return result;
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。