当前位置:网站首页>628. Maximum product of three numbers
628. Maximum product of three numbers
2022-07-06 16:07:00 【mrbone9】
Address :
Power button https://leetcode-cn.com/problems/maximum-product-of-three-numbers/
subject :
Here's an integer array nums , Find the largest product of three numbers in the array , And output this product .
Example 1:
Input :nums = [1,2,3] Output :6 |
Example 2:
Input :nums = [1,2,3,4] Output :24 |
Example 3:
Input :nums = [-1,-2,-3] Output :-6 |
Tips :
3 <= nums.length <= 104 -1000 <= nums[i] <= 1000 |
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/maximum-product-of-three-numbers
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas :
1. All positive numbers , Take the three largest numbers
2. All negative numbers , There will be no positive results , Also take the three largest numbers
3. There are positive and negative
3.1 Only 1 Negative numbers Take the three largest numbers
3.2 redundant 2 Negative numbers 2 Maximum negative numbers + Maximum integer , Three largest integers , Taking the maximum
So the last thing is to see which is the maximum :
Minimum two numbers + The maximum number , Three maximum numbers
Method 1 、 Sort
#define max(a,b) ( (a) > (b) ? (a) : (b) )
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int maximumProduct(int* nums, int numsSize){
qsort(nums, numsSize, sizeof(int), cmp);
return max(nums[0] * nums[1] * nums[numsSize-1], nums[numsSize-1] * nums[numsSize-2] * nums[numsSize-3]);
}
Method 2 、 Linear search
Sorting is lossy , If you can find what you need without sorting 5 Elements :2 Minimum ,3 The biggest
Then the performance will be improved
The title gives a numerical range :-1000 <= nums[i] <= 1000
So it can be assumed that :
1. The minimum value is initialized to 1000( Maximum )
2. The maximum value is initialized to -1000( minimum value )
If you find something smaller than the minimum value during traversal , Then update the minimum ; Similar to several other elements
#define MAXVALUE 1000
#define MINVALUE -1000
#define max(a,b) ( (a) > (b) ? (a) : (b) )
int maximumProduct(int* nums, int numsSize){
int min1 = MAXVALUE, min2 = MAXVALUE;
int max1 = MINVALUE, max2 = MINVALUE, max3 = MINVALUE;
for(int i=0; i<numsSize; i++)
{
if(min1 > nums[i])
{
min2 = min1;
min1 = nums[i];
}
else if(min2 > nums[i])
{
min2 = nums[i];
}
if(max1 < nums[i])
{
max3 = max2;
max2 = max1;
max1 = nums[i];
}
else if(max2 < nums[i])
{
max3 = max2;
max2 = nums[i];
}
else if(max3 < nums[i])
{
max3 = nums[i];
}
}
return max(min1 * min2 * max1, max1 * max2 * max3);
}
The method of linear search should be mastered
边栏推荐
- Opencv learning log 16 paperclip count
- Perform general operations on iptables
- 用C语言写网页游戏
- [exercise-1] (UVA 673) parentheses balance/ balanced brackets (stack)
- Opencv learning log 32 edge extraction
- [exercise -10] unread messages
- 【练习-10】 Unread Messages(未读消息)
- 信息安全-安全专业名称|CVE|RCE|POC|VUL|0DAY
- MySQL grants the user the operation permission of the specified content
- X-forwarded-for details, how to get the client IP
猜你喜欢
渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
Optimization method of path problem before dynamic planning
Borg maze (bfs+ minimum spanning tree) (problem solving report)
[exercise-5] (UVA 839) not so mobile (balance)
Nodejs+vue网上鲜花店销售信息系统express+mysql
快速转 TypeScript 指南
STM32 learning record: LED light flashes (register version)
Ball Dropping
Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
Penetration test (8) -- official document of burp Suite Pro
随机推荐
Find 3-friendly Integers
CEP used by Flink
China earth moving machinery market trend report, technical dynamic innovation and market forecast
【练习-6】(Uva 725)Division(除法)== 暴力
Borg maze (bfs+ minimum spanning tree) (problem solving report)
Matlab comprehensive exercise: application in signal and system
用C语言写网页游戏
Penetration testing (5) -- a collection of practical skills of scanning King nmap and penetration testing tools
Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
Analysis of protobuf format of real-time barrage and historical barrage at station B
China potato slicer market trend report, technical dynamic innovation and market forecast
Flink 使用之 CEP
HDU - 6024 building shops (girls' competition)
洛谷P1102 A-B数对(二分,map,双指针)
信息安全-威胁检测-flink广播流BroadcastState双流合并应用在过滤安全日志
VS2019初步使用
渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
[exercise-7] (UVA 10976) fractions again?! (fraction split)
Auto.js入门
信息安全-安全专业名称|CVE|RCE|POC|VUL|0DAY