本文主要是介绍LeetCode 628. 三个数的最大乘积 java版,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1. 官网:
. - 力扣(LeetCode)
2. 题目:
给你一个整型数组
nums
,在数组中找出由三个数组成的最大乘积,并输出这个乘积。示例 1:
输入:nums = [1,2,3] 输出:6示例 2:
输入:nums = [1,2,3,4] 输出:24示例 3:
输入:nums = [-1,-2,-3] 输出:-6提示:
3 <= nums.length <= 104
-1000 <= nums[i] <= 1000
3. 解:
思路:1. 给数组排序 (Arrays.sort),如果没有这个sort 你会用什么排序呢?
2. 取数组最大三个数相乘
3. 两个负数和一个正整数乘积,也需要加入判断
package com.nami.algorithm.study.maxnum;import java.util.Arrays;/*** 描述: 三个数的最大乘积** @Author: lbc* @Date: 2024-04-16 16:09* @email: 594599620@qq.com* @Description: keep coding*/
public class Solution {/*** 正常思路 排序后,最大三个数乘积即可* 如果没有例子,两个负数和一个整数 这个条件容易遗忘。就会变成 ·1.排序 ·2.return,取最大三个数的乘积** @param nums* @return*/public static int maximumProduct(int[] nums) {// DualPivotQuicksort 包含多种排序,根据数量判断使用 哪种排序算法// 这个sort 方法 比这道题nbArrays.sort(nums);int len = nums.length;return Math.max(nums[0] * nums[1] * nums[len - 1], nums[len - 1] * nums[len - 2] * nums[len - 3]);}public static void main(String[] args) {int[] nums = new int[]{1, 4, 6, 8, 320, 33, -200, -100, 20};System.out.println(maximumProduct(nums));}}
4. 解2:
解1的延伸,解1 是排序,找到最小数,次最小数,最大数,次最大数,次次最大数,一次遍历找出五个数,可以不用排序算法,再进行判断
1. 找出五个数
2. 同上,计算最大数乘积,与最小数 * 次最小数 * 最大数乘积,判断最大值
public static int maximumProduct(int [] nums) {// 最小值int min1 = Integer.MAX_VALUE;// 次最小值int min2 = Integer.MAX_VALUE;// 最大值int max1 = Integer.MIN_VALUE;// 次大值int max2 = Integer.MIN_VALUE;// 次次大int max3 = Integer.MIN_VALUE;for (int cur : nums) {if (cur < min1) {min2 = min1;min1 = cur;} else if (cur < min2) {min2 = cur;}if (cur > max1) {max3 = max2;max2 = max1;max1 = cur;} else if (cur > max2) {max3 = max2;max2 = cur;} else if (cur > max3) {max3 = cur;}}return Math.max(min1 * min2 * max1, max1 * max2 * max3);}
5. 排序算法: 冒泡,快排,堆排序,插入,希尔排序,桶?哪个是稳定排序?,还记得思路以及实现代码吗?
这篇关于LeetCode 628. 三个数的最大乘积 java版的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!