LeetCode题练习与总结：三个数的最大乘积--628

一、题目描述

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 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 语句用于从方法中返回一个值。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。