平顶山哪里做网站,驻马店住房和城乡建设厅网站,什么网站可以做外国生意,dede网站模板怎么安装一、题目描述
给你一个整型数组 nums #xff0c;在数组中找出由三个数组成的最大乘积#xff0c;并输出这个乘积。 示例 1#xff1a;
输入#xff1a;nums [1,2,3]
输出#xff1a;6示例 2#xff1a;
输入#xff1a;nums [1,2,3,4]
输出#xff1a;24示例 3在数组中找出由三个数组成的最大乘积并输出这个乘积。 示例 1
输入nums [1,2,3]
输出6示例 2
输入nums [1,2,3,4]
输出24示例 3
输入nums [-1,-2,-3]
输出-6提示
3 nums.length 10^4-1000 nums[i] 1000
二、解题思路
对数组进行排序。考虑到负数乘以负数会得到正数所以最大的乘积可能由两种情况产生 最大的三个正数相乘。最小的两个负数它们相乘得到正数和最大的正数相乘。 比较这两种情况得到的乘积取较大的一个作为结果。
三、具体代码
import java.util.Arrays;class Solution {public int maximumProduct(int[] nums) {// 对数组进行排序Arrays.sort(nums);// 数组长度int n nums.length;// 最大的三个数相乘int product1 nums[n - 1] * nums[n - 2] * nums[n - 3];// 最小的两个数可能为负数和最大的数相乘int product2 nums[0] * nums[1] * nums[n - 1];// 返回两种情况中较大的乘积return Math.max(product1, product2);}
}四、时间复杂度和空间复杂度
1. 时间复杂度 排序操作Arrays.sort(nums) 是一个通用的排序算法通常基于快速排序或归并排序实现其平均时间复杂度为 O(n log n)其中 n 是数组 nums 的长度。 计算乘积在排序后计算两个乘积 product1 和 product2 的时间复杂度是 O(1)因为这些操作都是常数时间的操作。
因此整个函数的时间复杂度主要取决于排序操作为 O(n log n)。
2. 空间复杂度 排序操作Arrays.sort(nums) 在最坏情况下可能需要 O(log n) 的空间复杂度这是由于递归调用栈的深度。不过对于大多数实现这个空间复杂度可以认为是 O(1)因为它们使用了原地排序算法。 临时变量除了输入数组 nums 以外我们使用了常数个额外空间n, product1, product2因此这部分的空间复杂度是 O(1)。
综合上述分析整个函数的空间复杂度是 O(1)即常数空间复杂度。
五、总结知识点 类定义 class 关键字用于定义一个类。Solution 是类的名称。 方法定义 public 关键字指定方法的访问修饰符表示该方法可以被任何其他类访问。int 表示方法返回值的类型。maximumProduct 是方法的名称。int[] nums 是方法的参数表示一个整型数组。 数组排序 Arrays.sort(nums) 是一个静态方法调用用于对数组 nums 进行排序。 数组操作 nums.length 用于获取数组的长度。nums[n - 1]、nums[n - 2]、nums[n - 3] 等用于访问数组中的元素。 基本数据类型和算术运算 int 是 Java 中的基本数据类型用于表示整数。* 是乘法运算符用于计算两个整数的乘积。 条件判断和返回值 Math.max(product1, product2) 是一个静态方法调用用于计算两个整数中的最大值。return 语句用于从方法中返回一个值。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
