Given an array ofnintegers wheren> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[i].
Solve itwithout divisionand 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 arraydoes notcount as extra space for the purpose of space complexity analysis.)
要考虑数组中0的个数，没有零，有一个0和有两个0的情况是不同的，如下:
class Solution {public:vector<int> productExceptSelf(vector<int>& nums) {int product=1;int nums_zero=0;int one_zero_pos=0;vector<int> output;for(int i=0;i<nums.size();++i){if(nums[i]==0 && nums_zero==0){nums_zero++;one_zero_pos=i;continue;}else if(nums[i]==0 && nums_zero==1){nums_zero++;break;}product=product*nums[i];}if(nums_zero==0){//没有0for(int i=0;i<nums.size();++i){//所有数的乘积除以该数output.push_back(product/nums[i]);}}else if(nums_zero==1){for(int i=0;i<nums.size();++i){//除了为0的位置的值不为0外，其他位置都是0if(i!=one_zero_pos)output.push_back(0);elseoutput.push_back(product);}}else{for(int i=0;i<nums.size();++i){//全是0output.push_back(0);}}return output;}};
版权声明：本文为博主原创文章，未经博主允许不得转载。
，当你能梦的时候就不要放弃梦
