leetcode关于数组的问题
2021-07-12 13:08
标签：.net tor 问题 正数 max 思路 href array 返回 [Leetcode] 628. 三个数的最大乘积 leetcode414-第三大的数 LeetCode 238 计算数组除自己外的元素乘积 LeetCode：152_Maximum Product Subarray | 最大乘积连续子数组 | Medium leetcode关于数组的问题 标签：.net tor 问题 正数 max 思路 href array 返回 原文地址：https://www.cnblogs.com/ranjiewen/p/9547308.html
解题思路：
这个一开始我是没想到思路的（除了遍历），因为有正负号的问题，后来看了一下别人的思路然后自己写的，思路是这样的：
三个数乘积最大只能有两种情况，
一种是三个最大正数直接乘起来最大，
另一种就是两个最小的负数乘起来再乘以一个最大的正数。
第一步：
跟前面的那个414.第三大的数一个思路，遍历找到最大的三个正数和最小的两个数。
第二步：
比较最大三个数的乘积和两个最小数乘以最大数的乘积谁大就返回谁。
解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。
返回第三大且又是唯一出现的数，这里涉及到了排序和去重，所以想到用set来做，因为set是自动去重并升序的容器，但有一点，访问set集合里的元素只能通过迭代器的形式进行访问，而不能通过下标。
class Solution {
public:
vectorint> productExceptSelf(vectorint>& nums) {
int n = nums.size();
vectorint> res(n, 1); // res有n个元素，值为1
if(n 1){
return nums;
}
for(int i = 1; i // res={1, n0, n0n1, n0n1n2};
res[i] = res[i-1] * nums[i-1];
}
int right = 1;
for(int i = n-2; i >= 0; i--){
right *= nums[i+1]; // right = n3,n3n2,n3n2n1
res[i] = res[i]*right;
}
return res;
}
};