2018年6月1日 星期五

[LeetCode] 628. Maximum Product of Three Numbers

轉自LeetCode

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:
  1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.
<Solution>

想法如下
  • 先對array做排序( O(nlogn))
  • 要特別注意的是有負數的情況,因為兩個負數相乘會變正數,所以最小的兩個負數和最大的正數三個相乘,也有可能比最大的三個正數相乘還大,這點要特別注意
code 如下

Java

kotlin

沒有留言:

張貼留言