题目描述
leetcode 第628题:三个数的最大乘积
给你一个整型数组 nums ,在数组中找出由三个数组成的最大乘积,并输出这个乘积。
示例:
输入:nums = [-100,-2,-3,1]
输出:300
解题方法
排序
参照题解
- 解题思路
将数组由小到大排序
求数组中三个最大数的乘积
求数组中两个最小数和一个最大数的乘积
最后求得三个数的最大乘积
- 复杂度
时间复杂度:O(nlogn),n为数组长度
空间复杂度:O(logn)
- 代码实现
python3
1 | class Solution: |
php
1 | class Solution { |
- 文字草稿
nums = [-100,-2,-3,1]
正序排列后得到[-100,-3,-2,1]
最大三个最大数的乘积为6=(-3)(-2)*1
两个最小数和一个最大数的乘积为300=(-100)(-3)*1
三个数的最大乘积即为300