算法分析：三個數的最大乘積

目錄

• 前言
• 第一種解法：先排序再找
• 第二種解法：線性布局
• 總結

前言

• 這題太簡單了，就是從數組裡找出三個數乘積最大
• 項目網址：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);
    }
}
           

總結

這道題簡單的不行，但是思想還是好的，能在檢索中排序就在檢索中排序。