赞
踩
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].
For example, given [1,2,3,4], return [24,12,8,6].
首先试了一下用两个for循环嵌套求解,时间复杂度是O(
数组a包含4个元素。
构建如下两个数组front和back:
数组名 | ||||
---|---|---|---|---|
front | 1 | a[0] | a[0] * a[1] | a[0] * a[1] * a[2] |
back | a[3] * a[2] * a[1] | a[3] * a[2] | a[3] | 1 |
通过将这两个数组的元素对应相乘,我们就能得到题目要求的,除了自身以外所有数组元素的乘积。
第一个数组front的构建方式是front[0]设置为1,从第2位开始,使用一个变量temProduct存储从a[0]到当前a[i -1]的乘积,每次都把这个乘积赋给front[i]。
第二个数组back的构建方式类似,不过从数组a最后一个元素开始,设置back[n - 1]为1(n 为数组a的大小),从倒数第二位开始,使用一个变量temProduct存储从a[n - 1]到当前a[i + 1]的乘积,每次都把这个乘积赋给back[i]。
最后将这两个数组元素对应相乘即得到结果。
为了节省空间,可以直接使用要返回的数组product作为那两个数组:首先是作为front数组,操作过程一样,然后作为back数组时是直接在当前元素上乘以temProduct。见参考代码1。
为了构建这两个数组需要两个for循环,它们的区别是遍历数组a的顺序不同,所以还可以合并,只用一个for循环同时进行对product[i] 和 product[n - i -1]的操作。见参考代码2。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> product(nums.size(), 1);
int temProduct = 1;
for (int i = 0; i < nums.size(); i++) {
product[i] = temProduct;
temProduct *= nums[i];
}
for (int i = nums.size() - 1, temProduct = 1; i >= 0; i--) {
product[i] *= temProduct;
temProduct *= nums[i];
}
return product;
}
};
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
int frontProduct = 1;
int backProduct = 1;
vector<int> product(n, 1);
for (int i = 0; i < n; i++) {
product[i] *= frontProduct;
frontProduct *= nums[i];
product[n - i - 1] *= backProduct;
backProduct *= nums[n - i - 1];
}
return product;
}
};
今天蛮失败的,自己没有想出这道题的解法,还是靠看其他人的解法才知道应该怎么做,不得不说,这道题的解法真的是很巧妙,让我大开眼界。还处于菜鸟的我真的要加油,多刷题,多见识见识了。
我填坑,我快乐,继续加油!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。