剑指offer51

剑指offer51：构建乘积数组 (Leetcode66)

题目描述

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],
其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。
不能使用除法。
（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）

解法一：基于两层for循环的暴力法(超出时间限制)

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int Size = A.size();
        vector<int> B(Size, 1);
        for (int i = 0; i<Size; i++)
        {
            for (int j = 0; j<Size; j++)
            {
                if (j != i)
                    B[i] *= A[j];
            }
        }
        return B;

    }
};

解法二：基于对称遍历 (执行用时48ms,内存消耗24.6MB)

/****************************************************************************************************
基于对称遍历 (执行用时48ms,内存消耗24.6MB)

通过 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]B[i]=A[0]×A[1]×…×A[i−1]×A[i+1]×…×A[n−1] ，
我们发现 B[i]B[i] 就是 A[i]A[i] 左边所有元素的积 乘 A[i]A[i] 右边所有元素的积。
这和分发糖果的操作思想一样，都是利用对称关系，经过两遍对称运算就能得到最终的结果。

思路：对称遍历
从左往右遍历累乘，结果保存在数组 retret 中，
此时 ret[i]ret[i] 表示，A[i]A[i] 左边所有元素的乘积
然后从右往左遍历累乘，获取A[i]A[i] 右边所有元素的乘积
两边遍历之后得到的 retret，就是最终结果
*******************************************************************************************************/
class Solution2 {
public:
    vector<int> constructArr(vector<int>& a) {
        int n = a.size();
        vector<int> ret(n, 1);
        int left = 1;
        for (int i = 0; i < n; i++) {
            ret[i] = left;
            left = left * a[i];
        }
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            ret[i] *= right;
            right *= a[i];
        }
        return ret;
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> nums, numsa;
    cout << "请输入数组的大小Size： "<< endl;
    int Size;
    cin >> Size;
    int Currval;
    cout << "请输入数组的元素： " << endl;
    for (int i = 0; i < Size; i++)
    {
        cin >> Currval;
        nums.push_back(Currval);
    }
    Solution answer;
    numsa=answer.multiply(nums);
    for (auto n : numsa)
        cout << n << " ";

    system("pause");
    return 0;
}