LeetCode628. Maximum Product of Three Numbers 解题

怼烎@ 2022-06-05 04:55 217阅读 0赞

先看看题目：

# 先看看题目： #

Given an integer array, find three numbers whose product is maximum and output the maximum product.

> 题目意思是说，给定一个整数的数组，找到三个能产生最大的积的数

看一下例子

> Example 1:  
> Input: \[1,2,3\]  
> Output: 6
> 
> Example 2:  
> Input: \[1,2,3,4\]  
> Output: 24

注意事项：

> The length of the given array will be in range \[3,104\] and all elements are in the range \[-1000, 1000\].  
> Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

1.  数组的长度不会超过104也不会少于3，其中元素的值在\[-1000,1000\]范围内
2.  他们的积不会超过32位整型数可以表示的范围，也就是说你可以用int 来保存结果

# 解题思路 #

我首先想到的方法就是先将他们排序，然后找最大的三个数相乘就是了。  
但是当我想用C++自带的sort()函数的时候，我却死活导不进去algorithm包，没办法，只好自己写排序了，我就找了个快速排序的算法写。  
然后我发现事情并没有那么简单，因为还存在负数，当遇到\[-9,-8,-2,-1,6\]这种情况的时候就不能单纯地找最大的三个了，因为负负得正，应该取最小的两个和最大的一个；同时如果我找好的三个数里头有一个为0，那就得换一个相邻的数代替。所以本以为寥寥几行可以搞定的代码最后写成了好几十行。

class Solution {
    public:
        int partition(vector<int> &array, int low, int high) {
            int key = array[low];
            while (low < high)
            {
                while (low < high && key <= array[high]) //如果array[high]大于键值，那么本就应该在键值右边
                    high--;  //因此将high下标向前移动，直至找到比键值小的值，此时交换这两个值
                swap(array[low], array[high]);
    
                while (low < high && key >= array[low])
                    low++;
                swap(array[low], array[high]);
            }
            return low;//返回key值的下标
        }
        void mySort(vector<int> &nums, int left, int right) {
            int pivot;
    
            if (left<right) {
                pivot = partition(nums, left, right);
                mySort(nums, left, pivot - 1);
                mySort(nums, pivot + 1, right);
            }
        }
        int maximumProduct(vector<int>& nums) {
            int result,resultA;
            int* count=new int[3];
            int i;
    
            //special case
            if(nums.size()==3)
            {
                result=nums[0]*nums[1];
                result*=nums[2];
                return result;
            }
            //give it a sort
            mySort(nums, 0, nums.size()-1);
            count[2]=nums[nums.size()-1];
            count[1]=nums[nums.size()-2];
            count[0]=nums[nums.size()-3];
            if(count[1]<0&&count[0]<0){
       // case -x, -x, x
                count[1]=nums[1];
                count[0]=nums[0];
            }
            for(i=0;i<3;i++){
       //if anyone is 0, get others
                if(count[i]==0)
                    count[i]=nums[nums.size()-4-i];
            }
            //count product
            result=count[0]*count[1];
            result*=count[2];
            //try the product of two -x
            resultA=nums[0]*nums[1];
            resultA*=count[2];
    
            return result>resultA?result:resultA;
        }
    };

# 更好的算法 #

leetcode比杭电OJ和POJ好的一个方面就是它在AC之后可以看到别人的代码，按效率排好序的，这样可以让人通过看更优秀的算法得到提高

这段代码的思路是按大小顺序维护五个变量：最大的三个(max3>max2>max1)和最小的两个(min1

class Solution {
    public:
        int maximumProduct(vector<int>& nums) {
            if(nums.size() == 3){
                return nums[0] * nums[1] * nums[2];
            }
            int max1 = INT_MIN;
            int max2 = INT_MIN;
            int max3 = INT_MIN;
    
            int min1 = INT_MAX;
            int min2 = INT_MAX;
    
            for(int i = 0; i < nums.size(); i++){
                if(nums[i] >= max1){
                    max3 = max2;
                    max2 = max1;
                    max1 = nums[i];
                }
                else if(nums[i] >= max2){
                    max3 = max2;
                    max2 = nums[i];
                }
                else if(nums[i] >= max3){
                    max3 = nums[i];
                }
    
                if(nums[i] <= min1){
                    min2 = min1;
                    min1 = nums[i];
                }
                else if(nums[i] <= min2){
                    min2 = nums[i];
                }
    
    
            }
            return max(max1 * max2 * max3, max1 * min1 * min2);
    
        }
    };