2023-12-12|閱讀時間 ‧ 約 4 分鐘

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

題目敘述

題目會給定一個整數陣列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

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.