算法分析:三个数的最大乘积

目录

前言

  • 这题太简单了,就是从数组里找出三个数乘积最大
  • 项目网址:https://leetcode-cn.com/problems/maximum-product-of-three-numbers/
    算法分析:三个数的最大乘积

第一种解法:先排序再找

  • 这个题目一般两种情况,一种是有负数,一种是没负数,先说没有负数的,很简单,就直接排序把后面三个乘起来,有负数,就要看,是一个负数还是两个负数还是多个负数,反正负数的乘积就是越小越好,因为排好序了,如果是负数就一定在前面,所以把前面两个数相乘,然后再乘最后一个最大的数,这样就是所能找到最大的乘积了。
  • 不多说上代码:
class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return  Math.max(nums[0] * nums[1] * nums[n-1], nums[n-1] * nums[n-2] * nums[n-3]);
    }
}

算法分析:三个数的最大乘积

第二种解法:线性布局

  • 这种解法只需要遍历一次,所以肯定比上一个排序之后要快,也很好理解,根据上面的思路,我们在遍历的时候把最小的两个值和最大的三个值存储起来,然后最后进行判断
  • 上代码
class Solution{
    public int maximumProduct(int[] nums) {
        int min1 = Integer.MAX_VALUE,min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE,max2 = Integer.MIN_VALUE,max3 = Integer.MIN_VALUE;
        for(int i : nums){
            if( i < min1){
                min2 = min1;
                min1 = i;
            }else if(i < min2){
                min2 = i;
            }
            if(i > max1){
                max3 = max2;
                max2 = max1;
                max1 = i;
            }else if(i>max2){
                max3 = max2;
                max2 = i;
            }else if(i>max3){
                max3 = i;
            }
        }
        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }
}

算法分析:三个数的最大乘积

总结

这道题简单的不行,但是思想还是好的,能在检索中排序就在检索中排序。

上一篇:三个数的最大乘积


下一篇:抛硬币