求数组中三个数的最大乘积(C++(易学习区))

给定一个整型数组,在数组中找出由三个数组成的最大乘积,并输出这个乘积。

示例 1:

输入: [1,2,3]
输出: 6
示例 2:

输入: [1,2,3,4]
输出: 24

#includelimits.h
C/C++中常量INT_MAX和INT_MIN分别表示最大、最小整数,头文件是limits.h。

INT_MAX = 2^31-1=2147483647;

INT_MIN= -2^31=-2147483648;

时间复杂度取决于排序:O(nlogn)

class Solution {
public:
    int maximumProduct(vectorint nums) {
      
     
      //先对这个数组排序
      sort(nums.begin(),nums.end());
      int a,b;
      // int a = INT_MIN, b = INT_MIN;有时候这样写!
      //如果前两位都小于0
      if(nums[0]0  nums[1]0)
      {
          a=nums[0]*nums[1]*nums[nums.size()-1];
      }
      //注意这里不是else,因为不管如何都要算b
          //如果只有一位小于0,或者都不小于0,
          b=nums[nums.size()-1]*nums[nums.size()-2]*nums[nums.size()-3];
          
      return max(a,b);
    }
};


C中的qsort()采用的是快排算法,C++的sort()则是改进的快排算法。两者的时间复杂度都是nlogn,但是实际应用中,sort()一般要快些,建议使用sort()。

先写到这里,明天补充!

第二种方法是,找到三个最大值和两个最小值进行比较

class Solution {
public:

    int maximumProduct(vectorint nums) {
        
        //三个最大值,初值定义为最小整数
        int max1 = INT_MIN;
        int max2 = INT_MIN;
        int max3 = INT_MIN;

        //两个最小值,初值定义为最大整数
        int min1 = INT_MAX;
        int min2 = INT_MAX;

        for(int a:nums)//记得定义a
        {
            if(amax1)
            {
                max3 = max2;
                max2 = max1;
                max1 = a;
            }else if(amax2)
            {
               max3 = max2;
               max2 = a; 
            }else if(amax3)
            {
                max3 = a;
            }

             if(amin1)
            {
                min2 = min1;
                min1 = a;
            }else if(amin2)
            {
                min2 = a;
            }
        }       
        return max(max1*max2*max3, min2*min1*max1);
    }
};

突然想到,这种方法是不是可以用到上一道题(求倒数第三个最大的数)里面,结果试了下不太行,因为这一个题是让求最大乘积,那么遇到相同的数字都可以被包含到那里面,而上一题不能有重复,重复的话就必须舍弃掉。

修改了很多次的失败品(针对上一题):

class Solution {
public:
    int thirdMax(vectorint nums) {

      
        //三个最大值,初值定义为最小整数
        int max1 = INT_MIN;
        int max2 = INT_MIN;
        int max3 = INT_MIN;

        //两个最小值,初值定义为最大整数
        int min1 = INT_MAX;
        int min2 = INT_MAX;

        for(int a:nums)//记得定义a
        {
            if(amax1 )
            {
                max3 = max2;
                max2 = max1;
                max1 = a;
            }else if(amax2  a !=max1)
            {
               max3 = max2;
               max2 = a; 
            }else if(amax3  a !=max1)
            {
                max3 = a;
            }

             if(amin1 )
            {
                min2 = min1;
                min1 = a;
            }else if(amin2  a!=min1)
            {
                min2 = a;
            }
        }
        if(min1==max2) return max1;
        if( nums[0]==nums[1]   nums[1]==nums[2]  ) return nums[0];
        return max3;


    }
};
最新回复(0)
/jishuZLrqDZ3uXwgKStIEsJrB018tEyda_2B3YuDYe2RbkVzp4_3D4858217
8 简首页