leetcode腾讯精选练习之除自身以外数组的乘积（十）

最长公共前缀

题目

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]

输出: [24,12,8,6]

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

思路

第一种思路O(n2):但是不符合题目要求

两层循环遍历，思路很简单不详细说了第一层遍历数组中中的每个数，第二层遍历求解除了本身之外的乘积。

第二种思路就是除法：也不符合题目要求

1.所有的数字相乘除去本身即可得到结果。

2.需要注意0的问题，如果有一个0，那么除了0那个为止之外的所有结果都是0，0位置处的结果是其他数字的乘积。如果有两个零，那么结果的所有值都是0。

第三种思路：

每个结果都是这个数左边的数字的乘积和右边的数字的乘积，然后在相乘的出来的。

所以先求出每个数字左遍的乘积，先后再求出右边的乘积，进行相乘即可得到结果。

举个例子：先列出数组[1,2,3,4]左边的数字的乘积如下所示：

1	2	3	4
1	1	2	6

然后在列出所有数字右遍的数的乘积如下所示：

1	2	3	4
24	12	4	1

然后将左边数字和右边数字的乘积列在一起,最后一行显示结果如果下所示：

1	2	3	4
1	1	2	6
24	12	4	1
24	12	8	6

将左边数字的乘积和右边数字的乘积相乘即可得到最终的结果。

代码

第一种思路：

vector<int> productExceptSelf(vector<int>& nums) {

    vector<int> res;

    int sz = nums.size();

    for (size_t i = 0; i < sz; i++)

    {

        int mul = 1;

        for (size_t j = 0; j < sz; j++)

        {

            if (i == j)

            {

                continue;

            }

            mul *= nums[j];

        }

        res.push_back(mul);

    }

}

第二种思路：

vector<int> productExceptSelf(vector<int>& nums) {

    vector<int> res;

    int sz = nums.size();

    int mul = 1;

    int zeroIndex = -1;

    int zeroNum = 0;

    for (size_t i = 0; i < sz; i++)

    {

        if (nums[i] != 0)

        {

            mul *= nums[i];

        }

        else

        {

            zeroNum++;

            if (zeroNum > 1)

            {

                res.resize(sz, 0);

                return res;

            }

            zeroIndex = i;

        }

    }

    if (zeroNum != 0)

    {

        res.resize(sz, 0);

        res[zeroIndex] = mul;

    }

    else

    {

        for (size_t i = 0; i < sz; i++)

        {

            res.push_back(mul / nums[i]);

        }

    }

    return res;

}

第三种思路：

vector<int> productExceptSelf(vector<int>& nums) {

    int sz = nums.size();

    vector<int> res(sz, 0);

    int tmp = 1;

    for (int i = 0; i < sz; i++) {

        res[i] = tmp;

        tmp *= nums[i];

    }

    tmp = 1;

    for (int i = sz - 1; i >= 0; i--) {

        res[i] *= tmp;

        tmp *= nums[i];

    }

    return res;

}

总结

这个题目总容易想到的就是前两种方法，第三种题目要求的方法还是需要多想想

巴特西

leetcode腾讯精选练习之除自身以外数组的乘积（十）

最长公共前缀

题目

思路

代码

总结

最新文章

热门文章