最大兩數的乘積 Leetcode 1464 Max Product of Two Elements in Array

Gayatri Malhotra on Unsplash

題目敘述

題目會給定一個整數陣列nums，要求我們找出最大的兩個整數a, b，返回(a-1) * (b-1)的乘積。

詳細的題目可在這裡看到

測試範例

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

Input: nums = [3,7]
Output: 12

約束條件

Constraints:

• 2 <= nums.length <= 500
• 1 <= nums[i] <= 10^3

演算法

第一直覺可能會想到先排序，再取最大的前兩個數字。

但是，其實不用排序，我們需要的只有前兩個最大的元素，分別用兩個變數first, second去記錄最大值 和 第二大的值，分別減一再相乘即可。

程式碼

cclass Solution(object):
　def maxProduct(self, nums):

　　first, second = 0, 0
　　
　　for number in nums:
　　　
　　　if number > first:
　　　　# update first largest and second largest
　　　　first, second = number, first
　　　　
　　　elif number > second:
　　　　# update second largest
　　　　second = number
　　
　　return (first - 1) * (second - 1)

複雜度分析

時間複雜度:

O( n ) 一次從左到右的線性掃描，長度和原本的陣列一樣長。

空間複雜度:

O( 1 ) 使用到的是固定大小的臨時變數，所佔用空間為常數級別。

關鍵知識點:

陣列的輸入資料打散的前提下，當所求為前K大或前K小的元素時，
聯想到O(n)時間的線性掃描演算法。
不需要真的去排序，省下整個陣列排序的成本O(n log n)。

Reference:

[1] Python/JS/Go/C++ O(n) by linear scan. [w/ Comment] - Maximum Product of Two Elements in an Array - LeetCode