题目描述

给定一个长度为 的无序数组 ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。

要求时间复杂度： ，空间复杂度： 。

解题思路

题目所要求的三个数的最大乘积，但要注意数组里的数字有正数有负数，所以结果得分类讨论。

有种情况可能是：三个最大的正数相乘得到的乘积；

还有种情况可能是一个最大的正数和两个最小的负数相乘得到的乘积；

或者还有可能是有零出现的情况，但仔细想想如果有零出现也包含在了前面说的2种情况当中，所以我们只需找出最大的三个正数和最小的两个负数即可。

那怎么找到最大的三个正数和最小的两个负数呢？

一个最简单的方法就是直接对数组来进行一遍从小到大的排序，数组最前面的2个数，和数组最后面的3个数就是我们要找的数字。但一般来说常见的排序算法的时间复杂度平均下来为O(N*logN)，是不满足题目的要求的，但是写下来提交到OJ上是可以通过的。。。所以这种方法就当重温了一遍排序算法吧。。。

方法一：排序

解题思路

这里就以快速排序算法为例进行编写代码。

快速排序的大体思路为：

先在要排序范围内的数组中，随机找一个数字，记为 pivot，之后遍历这个数组排序范围内的数字，小于 pivot 的数字放在数组的左边，等于 pivot 的数字放在数组的中间，大于 pivot 的数字放在数组的右边。

之后再对数组左边和右边范围内的数组进行上述步骤的快排，直到最后只剩下一个数字，即完成了快速排序算法。

在具体实现的时候，做了一些小技巧，详情请见代码注释。

有关排序算法的一些解释，可以参考之前写过的一篇文章：部分排序算法的总结

代码示例

import java.util.*;


public class Solution {
    /**
     * 最大乘积
     * @param A int整型一维数组 
     * @return long长整型
     */
    public long solve (int[] nums) {
        if (nums == null || nums.length < 3) {
            return 0;
        }

        // 对 nums 进行从小到大的顺序的快速排序
        quickSortMain(nums);

        // 最小的2个数，和最大的1个数，相乘
        long res1 = (long) nums[0] * nums[1] * nums[nums.length - 1];
        // 最大的3个数，相乘
        long res2 = (long) nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];
        return Math.max(res1, res2);
    }



    /**
     * 对 nums 进行从小到大的排序。 以快速排序的算法进行
     */
    public void quickSortMain(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

        quickSort(nums, 0, nums.length - 1);
    }

    /**
     * 在 nums[left...right] 范围上进行快速排序
     *
     * @param nums  要排序的数组
     * @param left  数组上的排序范围的 左闭区间
     * @param right 数组上的排序范围的 有闭区间
     */
    public void quickSort(int[] nums, int left, int right) {
        // 只有 1 个元素， 或 范围不合理就排序结束
        if (left >= right) {
            return;
        }

        // 在范围里，随机抽取一个下标， 作为以后比较的基准值pivot。
        int randomIndex = (int) (left + (Math.random() * (right - left)));
        // 抽取的数字，和数组中排序范围的最右边的数字，进行交换
        swap(nums, right, randomIndex);
        // 基准值 pivot； 等于 pivot 的数字放在数组的中间； 小于 pivot 的数字放在数组的左边； 大于 pivot 的数字放在数组的右边
        int pivot = nums[right];
        // 下标值。 [left...minRight] 上的数字是 小于 pivot 的。
        int minRight = left - 1;
        // 下标值。 [maxLeft...right) 上的数字上 大于 pivot 的。
        int maxLeft = right;

        int cur = left;
        while (cur < maxLeft) {
            if (nums[cur] < pivot) {
                // 当前遍历到的值， 小于 pivot 的情况
                // 当前值 和 小于范围里后一个位置的值， 交换位置。  然后小于范围扩大 1 位； 当前下标往前走 1 位。
                swap(nums, cur++, ++minRight);
            } else if (nums[cur] > pivot) {
                // 当前遍历到的值， 大于 pivot 的情况
                // 当前值 和 大于范围里前一个位置的值， 交换位置。 然后大于范围扩大 1 位； 当前下标不变，因为交换过来的值仍然没有进行比较。
                swap(nums, cur, --maxLeft);
            } else {
                // 当前遍历到的值， 等于 pivot 的情况
                // 当前下标往前走 1 位即可
                cur++;
            }
        }

        // 处理 pivot 在最右边的变化
        swap(nums, maxLeft++, right);

        // 在小于 pivot 的范围里，接着做快速排序
        quickSort(nums, left, minRight);
        // 在大于 pivot 的范围里，接着做快速排序
        quickSort(nums, maxLeft, right);
    }

    /**
     * 交换 nums[i] 和 nums[j] 这 2 个数字
     */
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度分析

时间复杂度：O(N*logN)

这里采用的递归写法，可以用 master 定理来求解他的时间复杂的。

有关 master 的介绍，可以参考这篇文章里的递归方法中复杂度分析的部分：https://blog.nowcoder.net/n/05f504ff9a344df9ba7c295d4132be51

即： T(n) = a * T(n / b) + O(n^d)

这里 a = 2、b = 2、 d = 1。

属于： O(N^d * logN) 的情况，所以，时间复杂度为 O(N*logN)。

空间复杂度：O( logN )

就是在找中点的时候用了一定的空间存储。可以类似于每次都二分下去查找，则总共就有 logN 次下去查找的过程。所以，总的空间复杂度为 O(logN)。

方法二：直接找值

解题思路

另一种方法就是只遍历一遍数组，在遍历的过程就把最大的三个正数和最小的两个负数给找出来了。

具体做法就是把遍历到的每一个数字依次和目标值做比较即可，看下面的图解和代码注释思路会更清晰一些：

代码示例

import java.util.*;


public class Solution {
    /**
     * 最大乘积
     * @param A int整型一维数组 
     * @return long长整型
     */
    public long solve (int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // 最大的第1个正数
        int posMax1 = Integer.MIN_VALUE;
        // 最大的第2个正数
        int posMax2 = Integer.MIN_VALUE;
        // 最大的第3个正数
        int posMax3 = Integer.MIN_VALUE;
        // 最小的第1个负数
        int negMin1 = Integer.MAX_VALUE;
        // 最小的第2个负数
        int negMin2 = Integer.MAX_VALUE;

        for (int num : nums) {
            if (num > posMax1) {
                // 找到了第1个最大的正数，最大的第2、3个整数跟着更新
                int temp = posMax1;
                posMax1 = num;
                posMax3 = posMax2;
                posMax2 = temp;
            } else if (num > posMax2) {
                // 找到了第2个最大的正数，最大的第3个整数跟着更新
                posMax3 = posMax2;
                posMax2 = num;
            } else if (num > posMax3) {
                // 找到了第3个最大的正数，只更新他即可
                posMax3 = num;
            }

            if (num < negMin1) {
                // 找到了第1个最小的负数，最小的第2个负数跟着更新
                negMin2 = negMin1;
                negMin1 = num;
            } else if (num < negMin2) {
                // 找到了第2个最小的负数，只更新他即可
                negMin2 = num;
            }
        }

        // 三个最大的正数相乘得到的结果
        long res1 = (long) posMax1 * posMax2 * posMax3;
        // 第1个最大的正数，和2个最小的负数相乘得到的结果
        long res2 = (long) negMin1 * negMin2 * posMax1;

        // 两者之间取最大值就是所得答案
        return Math.max(res1, res2);
    }
}

复杂度分析

时间复杂度：O(N)

整个过程就是遍历一遍数组找一些最大值和最小值的过程，在遍历的过程中时间复杂度就是 O(N)。

空间复杂度：O(1)

整个过程只用了有限的几个记录最大值最小值的变量，和题目的数据数量N没有关系，所以最后空间复杂度为常数的级别的，即：O(1)。