前言：
欢迎阅读LeetCode每日一题系列，这个系列将会以每日一道算法题的形式，给大家带来详细的LeetCode算法题的解题思路和编写过程，带你一路过关斩将，拿下这些看似难懂的算法题！今天给大家分享的是三个数的最大乘积！废话不多说，先上题目！
1.1 题目要求
题目类型：三个数的最大乘积
题目内容：整型数组nums，在数组中找出由三个数字组成的最大乘积，并输出这个乘积
注意事项：乘积不会越界
重点考查：线性扫描
1.2 解题方法
怎么样？看完了题目，是不是感觉一头雾水；没关系，看一看解题思路，相信你会有所启发！
1.2.1 解题思路
例如一个整型数组元素为：[1, 2, 3, 4 ] ，那么最大乘积就是 2 * 3 * 4 = 24
- 若整型数组的元素都为整数，那么只需要求出三个大数的乘积，即为最大乘积；
注意：这里三个大数是指在整型数组的中绝对值排在前三的元素
- 若整型数组的元素都为负数，那么仍然需要求出三个大数的乘积
注意：由于三个负数相乘，其结果仍为负数，负数的绝对值越大，其实际值越小，因此这里三个大数是指在整型数组的中绝对值排在倒数三位的元素
例如整型数组 nums的元素为：[-4, -3, -2, -1]，求三个数的最大乘积时，选取的乘数是-3, -2, -1，而不是 -4, -3, -2
- 若整型数组的元素有正有负时，则需要在负数中选择两个小数(即绝对值排在前两个的元素), 在正数中选择一个最大数；
因此可以分为两种情况:
- 第一种情况：数组元素全为正数或者负数, 选取数组中排前三的元素，三者求乘积
- 第二种情况：数组元素有正有负，选取数组中的负数绝对值排前二的元素, 正数中最大元素，三者求乘积
1.2.2 代码实现
1.使用快速排序查找
这里我们使用JDK1.8 API中提供的数组工具类提供的排序方法，即双轴快速排序算法
- Arrays数组工具类的sort()方法源码
package java.util;
//数组工具类
public class Arrays {
/**
* 将指定的数组按升序排列
*
* 注意: 该排序算法为双轴快排 (由Vladimir Yaroslavskiy和Jon Bentley和Joshua Bloch编写)
* 该算法在大规模数据下的时间复杂度为O(n log(n)), 导致其他快速排序降级为二次性能, 通常比传统的(单轴)快速排序实现更快
*
* @param 被排序的数组
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
}
- 测试代码
package com.kuang.leetcode6;
import java.util.Arrays;
/**
* @ClassName MaxProduct
* @Description 整型数组中三个数的最大乘积
* @Author 狂奔の蜗牛rz
* @Date 2021/8/18
*/
public class MaxProduct {
//主方法测试
public static void main(String[] args) {
//初始化整型数组元素
//第一种情况: 数组元素都为正数
int[] arr1 = {1,2,3,4,5,6};
//第一种情况: 数组元素都为负数
int[] arr2 = {-6,-5,-4,-3,-2,-1};
//第二种情况: 数组元素有负有正
int[] arr3 = {-6,5,-4,3,-2,1};
//调用sort方法(快速排序算法), 获取最大乘积
System.out.println("使用快速排序算法:");
//预估结果为: 4*5*6=120
System.out.println(sort(arr1)); // 测试结果: 120
//预估结果为: (-3)*(-2)*(-1)=-6
System.out.println(sort(arr2)); // 测试结果: -6
//预估结果为: (-6)*(-4)*5=120
System.out.println(sort(arr3)); // 测试结果: 120
}
/**
* 使用快速排序查找最大乘积
* 将整型数组的元素进行排序, 并返回最大乘积
* @param nums 待排序的整型数组
* @return 最大乘积值
*/
public static int sort(int[] nums) {
/**
* 直接使用Arrays数组工具类的sort方法
* (底层是双轴快速排序算法, 其时间复杂度为O(n log(n)))
*/
Arrays.sort(nums);
/**
* 有没有比它时间复杂度更低的算法？
* 不使用排序, 使用线性扫描
*/
//变量n为整型数组的长度
int n = nums.length;
//返回值为两种情况下乘积的最大值(使用Math的max方法求最大值)
/**
* 第一种情况, 数组元素中有正有负:
* 经过快速排序后, 数组元素升序排列; 此时nums[0]中存放的负数中最小的元素,
* nums[1]中存放的是负数中第二小的元素, 而nums[n-1]中存放的是正数中最大的元素,
* 将三个元素求取乘积: 即 nums[0] * nums[1] * nums[n-1]
* 第二种情况, 数组元素中只有正数或者负数:
* 经过快速排序后, 数组元素升序排列,
* 此时nums[n-1], nums[n-2]和nums[n-3]中存储的分别是数组元素中最大值, 次大值和第三大值;
* 将三个元素求取乘积: 即 nums[n-1] * nums[n-2] * nums[n-3];
*
* 无论整型数组中全是正数或者负数, 或者有正有负, 我们只需将数组中这两种情况下的最大值分别求出，然后比较出真正的最大值
*/
return Math.max(nums[0] * nums[1] * nums[n-1], nums[n-1] * nums[n-2] * nums[n-3]);
}
}
- 测试结果
结果：测试结果与预期结果相同！
2.使用线性扫描查找
- 测试代码
package com.kuang.leetcode6;
import java.util.Arrays;
/**
* @ClassName MaxProduct
* @Description 整型数组中三个数的最大乘积
* @Author 狂奔の蜗牛rz
* @Date 2021/8/18
*/
public class MaxProduct {
//主方法测试
public static void main(String[] args) {
//初始化整型数组元素
//第一种情况: 数组元素都为正数
int[] arr1 = {1,2,3,4,5,6};
//第一种情况: 数组元素都为负数
int[] arr2 = {-6,-5,-4,-3,-2,-1};
//第二种情况: 数组元素有负有正
int[] arr3 = {-6,5,-4,3,-2,1};
//调用getMaxMin方法(线性查找算法), 获取最大乘积
System.out.println("使用线性扫描算法:");
//预估结果为: 4*5*6=120
System.out.println(getMaxMin(arr1)); // 测试结果: 120
//预估结果为: (-3)*(-2)*(-1)=-6
System.out.println(getMaxMin(arr2)); // 测试结果: -6
//预估结果为: (-6)*(-4)*5=120
System.out.println(getMaxMin(arr3)); // 测试结果: 120
}
/**
* 双轴快速排序的时间复杂度为O(n log(n)), 有没有比它时间复杂度更低的算法？
* 解决方案: 不使用排序, 使用线性扫描, 时间复杂度为O(n)
*/
/**
* 使用线性扫描查找最大乘积
* @param nums 待排序的整型数组
* @return 最大乘积值
*/
public static int getMaxMin(int[] nums) {
/**
* 变量min1表示整型数组中第一小元素值, min2表示第二小元素值;
* 注意: 这里min1和min2虽然表示小元素值, 但是其初值却为Integer.MAX_VALUE
*/
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
/**
* max1,max2和max3分别表示整型数组中第一大, 第二大和第三大元素值;
* 注意: 这里max1, max2和max3虽然表示大元素值, 但是其初值却为Integer.MIN_VALUE
*/
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
//遍历nums整型数组, x为整型数组中的每个元素值
for (int x : nums) {
//判断x(当前元素值)是否小于min1(默认第一小值)
if(x < min1) {
//若x值小于min1, 将min1(第一小值)赋值给min2(第二小值)
min2 = min1;
//然后将x(真实最小值)赋值给min1(默认第一小值)
min1 = x;
//若x值大于min1, 则继续判断x(当前元素值)是否小于min2(默认第二小值)
} else if(x < min2) {
//若x值小于min2, 则将x(实际第二小值)赋给min2(默认第二小值)
min2 = x;
}
//判断x(当前元素值)是否大于max1(默认第一大值)
if(x > max1) {
//若x大于max1, 将max2(默认第二大值)赋值给max3(默认第三大值)
max3 = max2;
//然后将max1(默认第一大值)赋值给max2(默认第二大值)
max2 = max1;
//最后将x(当前元素值)赋值给max1(默认第一大值)
max1 = x;
//若x小于max1, 判断x(当前元素值)是否大于max2(默认第二大值)
} else if( x > max2) {
//若x大于max2, 将max2(默认第二大值)赋值给max3(默认第一大值)
max3 = max2;
//然后将x(当前元素值)赋值给max2(默认第二大值)
max2 = x;
//若x小于max2, 判断x(当前元素值)是否大于max3(默认第三大值)
} else if( x > max3) {
//若x大于max2, 将x(当前元素值)赋值给max3(默认第三大值)
max3 = x;
}
}
//最后将两种情况下的最大乘积比较, 将实际最大乘积进行返回
return Math.max(min1 * min2 * max1, max1 * max2 * max3);
}
- 测试结果
结果：测试结果与预期结果相同！
好了，今天LeetCode每日一题—三个数的最大乘积到这里就结束了，欢迎大家学习和讨论，点赞和收藏！
参考视频链接：https://www.bilibili.com/video/BV1Ey4y1x7J3 (国内算法宝典-LeetCode算法50讲)