【剑指offer】66构建乘积数组 阳光穿透心脏的1/2处 2021-10-03 02:20 271阅读 0赞 [面试题66. 构建乘积数组][66.] 难度简单15 给定一个数组 `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]`。不能使用除法。 **示例:** 输入: [1,2,3,4,5] 输出: [120,60,40,30,24] **提示:** * 所有元素乘积之和不会溢出 32 位整数 * `a.length <= 100000` `解题思路:` `先求左边的乘积(当前下标之前的乘积)` ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70][] `再求右边的乘积(当前下标之后的乘积)` ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 1][] `然后相乘` ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 2][] class Solution { public int[] constructArr(int[] a) { int []array = new int[a.length]; int left = 1; for(int i = 0;i<array.length;i++){ array[i] = left; left*=a[i]; } int right = 1; for(int i = array.length-1;i>=0;i--){ array[i] *= right; right *= a[i]; } return array; } } [66.]: https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/ [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70]: /images/20211003/cc133d432d1346c5942d51655ecced46.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 1]: /images/20211003/8bca52881a914ee9b1396a7a9c0b7b91.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 2]: /images/20211003/ce82120d38f646eab5064d0e685f3697.png
还没有评论,来说两句吧...