LeetCode-628. Maximum Product of Three Numbers

LeetCode►ACM ACM, LeetCode 评论

题目

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

Example 1:

1
2
Input: [1,2,3]
Output: 6

Example 2:

1
2
Input: [1,2,3,4]
Output: 24

Note:

1
2
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

/*
 * 设计知识点：
            快速排序（减少时间复杂度，减少时间）

 *  错误用例
 *  Input:
    [-4,-3,-2,-1,60]
    Output:
    120
    Expected:
    720
 * 错误：
 *          1. 测试用例中出现了负数导致产品的值出现了比较错误，使实际的输出值不是最大
 * 解决方案
 *          1.采用将全部的数值转换成整数的方案
 * 缺点
 *          1.会使得最后的结果出错(错误无法避免，切换解决方案)
 *方案2：
 *          分别判断，分别返回
 *
 * 错误用例
 * [722,634,-504,-379,163,-613,-842,-578,750,951,-158,30,-238,-392,-487,-797,-157,-374,999,-5,-521,-879,-858,382,626,803,-347,903,-205,57,-342,186,-736,17,83,726,-960,343,-984,937,-758,-122,577,-595,-544,-559,903,-183,192,825,368,-674,57,-959,884,29,-681,-339,582,969,-95,-455,-275,205,-548,79,258,35,233,203,20,-936,878,-868,-458,-882,867,-664,-892,-687,322,844,-745,447,-909,-586,69,-88,88,445,-553,-666,130,-640,-918,-7,-420,-368,250,-786]
 *错误2 ：
 *      低估了数组的大小
 *解决方案:
 *     扩充int到long
 * 看了下大佬的还真是棒 而且简单的很 site:http://www.cnblogs.com/grandyang/p/7084957.html
 * */
#include <stdio.h>
void quiksort(int a[],int low,int high)
{
    int i = low;
    int j = high;
    int temp = a[i];

    if( low > high)
    {
        return ;
    }
    while(i < j)
    {
        while((a[j] >= temp) && (i < j))
        {
            j--;
        }
        a[i] = a[j];
        while((a[i] <= temp) && (i < j))
        {
            i++;
        }
        a[j]= a[i];
    }
    a[i] = temp;
    quiksort(a,low,i-1);
    quiksort(a,j+1,high);
}
int maximumProduct(int* nums, int numsSize) {
    quiksort(nums,0,numsSize-1);
//    当nums[numsSize-1]<=0 即全部均小于零 则 nums[0]*nums[1]*nums[numsSize-1]最大
    /*if(nums[numsSize-1]<=0)
    {
        return  nums[0]*nums[1]*nums[numsSize-1];
    } else if(nums[numsSize-2]<0)
    {
//        此时 nums[numsSize-1]>0 &&nums[numsSize-2]<0] 此时返回nums[0]*nums[1]*nums[numsSize-1]
        return  nums[0]*nums[1]*nums[numsSize-1];
    } else if(nums[numsSize-2]==0) {
//        此时直接返回0
        return 0;
    }else if(nums[numsSize-3]<=0)
    {
        return nums[numsSize-1]*nums[numsSize-2]*nums[numsSize-3];
    }
    return nums[numsSize-3]*nums[numsSize-2]*nums[numsSize-1];*/
    int max=0,max1;
    max=nums[numsSize-1]*nums[0]*nums[1];
    max1=nums[numsSize-1]*nums[numsSize-2]*nums[numsSize-3];
    if(max>max1)
    {
        return max;
    } else
    {
        return  max1;
    }

}
int main()
{
    int nums[]={722,634,-504,-379,163,-613,-842,-578,750,951,-158,30,-238,-392,-487,-797,-157,-374,999,-5,-521,-879,-858,382,626,803,-347,903,-205,57,-342,186,-736,17,83,726,-960,343,-984,937,-758,-122,577,-595,-544,-559,903,-183,192,825,368,-674,57,-959,884,29,-681,-339,582,969,-95,-455,-275,205,-548,79,258,35,233,203,20,-936,878,-868,-458,-882,867,-664,-892,-687,322,844,-745,447,-909,-586,69,-88,88,445,-553,-666,130,-640,-918,-7,-420,-368,250,-786};
    int numsSize= sizeof(nums)/ sizeof(int);
    printf("%d",maximumProduct(nums,numsSize));
    return 0;
}

aclihuiWeb Developer & Designer

相信未来