238. 除自身以外数组的乘积 Product of Array Except Self
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
提示：
2 <= nums.length <= 10^5-30 <= nums[i] <= 30- 保证 数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
代码1： 暴力循环
package main import "fmt" func productExceptSelf(nums []int) []int { n := len(nums) ans := make([]int, n) for i := 0; i < n; i++ { ans[i] = 1 for j := 0; j < n; j++ { if j != i { ans[i] *= nums[j] } } } return ans } func main() { nums := []int{1,2,3,4} fmt.Println(productExceptSelf(nums)) nums = []int{-1,1,0,-3,3} fmt.Println(productExceptSelf(nums)) }
代码2： 前缀积和后缀积
package main import "fmt" func productExceptSelf(nums []int) []int { n := len(nums) prefix := make([]int, n) suffix := make([]int, n) ans := make([]int, n) prefix[0] = 1 for i := 1; i < n; i++ { prefix[i] = prefix[i-1] * nums[i-1] } suffix[n-1] = 1 for i := n - 2; i >= 0; i-- { suffix[i] = suffix[i+1] * nums[i+1] } for i := 0; i < n; i++ { ans[i] = prefix[i] * suffix[i] } return ans } func main() { nums := []int{1, 2, 3, 4} fmt.Println(productExceptSelf(nums)) nums = []int{-1, 1, 0, -3, 3} fmt.Println(productExceptSelf(nums)) }
代码3： 优化掉前缀数据的空间
package main import "fmt" func productExceptSelf(nums []int) []int { n := len(nums) ans := make([]int, n) ans[0] = 1 for i := 1; i < n; i++ { ans[i] = ans[i-1] * nums[i-1] } suffix := 1 for i := n-1; i >= 0; i-- { ans[i] *= suffix suffix *= nums[i] } return ans } func main() { nums := []int{1, 2, 3, 4} fmt.Println(productExceptSelf(nums)) nums = []int{-1, 1, 0, -3, 3} fmt.Println(productExceptSelf(nums)) }
输出：
[24 12 8 6]
[0 0 9 0 0]
240. 搜索二维矩阵 II Search A 2d Matrix ii
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-10^9 <= matrix[i][j] <= 10^9- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9
相关题目：
74. 搜索二维矩阵 Search A 2d-Matrix 🌟🌟
代码1： 暴力法
package main import "fmt" func searchMatrix(matrix [][]int, target int) bool { m := len(matrix) n := len(matrix[0]) for i := 0; i < m; i++ { for j := 0; j < n; j++ { if matrix[i][j] == target { return true } } } return false } func main() { matrix := [][]int{ {1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}} fmt.Println(searchMatrix(matrix, 5)) fmt.Println(searchMatrix(matrix, 20)) }
代码2： 缩小搜索范围
package main import "fmt" func searchMatrix(matrix [][]int, target int) bool { m := len(matrix) n := len(matrix[0]) i, j := 0, n-1 for i < m && j >= 0 { if matrix[i][j] == target { return true } else if matrix[i][j] < target { i++ } else { j-- } } return false } func main() { matrix := [][]int{ {1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}} fmt.Println(searchMatrix(matrix, 5)) fmt.Println(searchMatrix(matrix, 20)) }
代码3： 二分查找
package main import "fmt" func searchMatrix(matrix [][]int, target int) bool { m, n := len(matrix), len(matrix[0]) if m == 0 || n == 0 { return false } left, right := 0, m*n-1 for left <= right { mid := left + (right-left)/2 row, col := mid/n, mid%n if matrix[row][col] == target { return true } else if matrix[row][col] < target { left = mid + 1 } else { right = mid - 1 } } return false } func main() { matrix := [][]int{ {1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}} fmt.Println(searchMatrix(matrix, 5)) fmt.Println(searchMatrix(matrix, 20)) }
输出：
true
false
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
