LeetCode实战：除自身以外数组的乘积

背景

为什么你要加入一个技术团队？
如何加入 LSGO 软件技术团队？
我是如何组织“算法刻意练习活动”的？
为什么要求团队的学生们写技术Blog

题目英文

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:

Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

题目中文

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

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

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

进阶：

你可以在常数空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

算法实现

public class Solution
{public int[] ProductExceptSelf(int[] nums){int len = nums.Length;int[] output1 = new int[len];//正向乘积int[] output2 = new int[len];//反向乘积output1[0] = 1;output2[len - 1] = 1;for (int i = 1; i < len; i++){output1[i] = output1[i - 1]*nums[i - 1];output2[len - i - 1] = output2[len - i]*nums[len - i];}for (int i = 0; i < len; i++){output1[i] *= output2[i];}return output1;}
}

实验结果

状态：通过
17 / 17 个通过测试用例
执行用时: 304 ms, 在所有 C# 提交中击败了 100.00% 的用户
内存消耗: 34.6 MB, 在所有 C# 提交中击败了 100.00% 的用户

提交结果

相关图文

1. “数组”类算法

LeetCode实战：三数之和
LeetCode实战：最接近的三数之和
LeetCode实战：求众数
LeetCode实战：缺失的第一个正数
LeetCode实战：快乐数
LeetCode实战：寻找两个有序数组的中位数
LeetCode实战：盛最多水的容器
LeetCode实战：删除排序数组中的重复项
LeetCode实战：搜索旋转排序数组
LeetCode实战：螺旋矩阵
LeetCode实战：螺旋矩阵 II
LeetCode实战：买卖股票的最佳时机
LeetCode实战：买卖股票的最佳时机 II

2. “链表”类算法

LeetCode实战：两数相加
LeetCode实战：删除链表的倒数第N个节点
LeetCode实战：两两交换链表中的节点
LeetCode实战：旋转链表
LeetCode实战：环形链表

3. “栈”类算法

LeetCode实战：有效的括号
LeetCode实战：最长有效括号
LeetCode实战：逆波兰表达式求值

4. “队列”类算法

LeetCode实战：设计循环双端队列
LeetCode实战：滑动窗口最大值
LeetCode实战：整数反转
LeetCode实战：字符串转换整数 (atoi)

5. “递归”类算法

LeetCode实战：爬楼梯

6. “位运算”类算法

LeetCode实战：只出现一次的数字
LeetCode实战：格雷编码

7. “字符串”类算法

LeetCode实战：反转字符串
LeetCode实战：翻转字符串里的单词
LeetCode实战：最长公共前缀
LeetCode实战：字符串相加
LeetCode实战：字符串相乘

8. “树”类算法

LeetCode实战：相同的树
LeetCode实战：对称二叉树
LeetCode实战：二叉树的最大深度
LeetCode实战：二叉树中的最大路径和
LeetCode实战：将有序数组转换为二叉搜索树

9. “哈希”类算法

LeetCode实战：两数之和

10. “排序”类算法

LeetCode实战：合并两个有序数组
LeetCode实战：合并两个有序链表
LeetCode实战：合并K个排序链表

11. “搜索”类算法

LeetCode实战：搜索二维矩阵
LeetCode实战：子集

12. “动态规划”类算法

LeetCode实战：最长回文子串
LeetCode实战：最大子序和
LeetCode实战：不同路径

13. “回溯”类算法

LeetCode实战：全排列

14. “数值分析”类算法

LeetCode实战：回文数
LeetCode实战：x 的平方根