LeetCode-628. Maximum Product of Three Numbers

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

Note:

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.

分析

这是一道读题的题目,这是第二次出现快速排序,分析在注释中。

代码+注释


/* * 设计知识点: 快速排序(减少时间复杂度,减少时间) * 错误用例 * 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; }
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注