用c++写一条题目
时间: 2023-07-01 10:14:34 浏览: 69
好的,下面为你提供一条题目:
【题目描述】
给定一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
【示例】
输入: [1,2,3,4]
输出: [24,12,8,6]
【说明】
请不要使用除法,且在 O(n) 时间复杂度内完成此题。
【提示】
1. 题目中 n > 1,因此不需要考虑数组长度为 1 的情况。
2. 不能使用除法,因此需要考虑其他方法来计算每个 output[i] 的值。
3. 在 O(n) 时间复杂度内完成此题,因此需要注意算法的时间复杂度。
【参考答案】
以下是一种时间复杂度为 O(n) 的解法,可以通过本题:
```c++
#include <iostream>
#include <vector>
using namespace std;
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> output(n, 1);
int left = 1, right = 1;
for (int i = 0; i < n; i++) {
output[i] *= left;
left *= nums[i];
output[n-i-1] *= right;
right *= nums[n-i-1];
}
return output;
}
int main() {
vector<int> nums = {1, 2, 3, 4};
vector<int> output = productExceptSelf(nums);
for (auto i : output) {
cout << i << " ";
}
cout << endl;
return 0;
}
```
在这个算法中,我们首先定义一个长度为 n 的 output 数组,并将其初始化为 1。然后,我们使用两个变量 left 和 right 分别记录当前元素左侧和右侧的乘积。在每次循环中,我们将 output 数组中的元素乘以 left 和 right,然后更新 left 和 right 的值。最后,我们返回 output 数组即可。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)