最大兩數的乘積 Leetcode 1464 Max Product of Two Elements in Array
閱讀時間約 3 分鐘
題目敘述
題目會給定一個整數陣列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 <= 5001 <= 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:
90會員
425內容數
由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。
留言0
查看全部
你可能也想看
Google News 追蹤
徵的就是你 🫵 超ㄅㄧㄤˋ 獎品搭配超瞎趴的四大主題，等你踹共啦！還有機會獲得經典的「偉士牌樂高」喔！馬上來參加本次的活動吧！
隨著理財資訊的普及，越來越多台灣人不再將資產侷限於台股，而是將視野拓展到國際市場。特別是美國市場，其豐富的理財選擇，讓不少人開始思考將資金配置於海外市場的可能性。
然而，要參與美國市場並不只是盲目跟隨標的這麼簡單，而是需要策略和方式，尤其對新手而言，除了選股以外還會遇到語言、開戶流程、Ap
給定一個長度為 n 的整數數組 nums 和一個整數target，在 nums 中找到三個整數，使得總和最接近target。傳回三個整數的總和。可以假設每個輸入都有一個解決方案。
一、基本算術運算符號
加法：+
減法：-
乘法：*
除法：/（返回浮點數）
a = 1
b = 2
print( a + b ) # 加法 輸出：3
print( a - b ) # 減法 輸出：-1
print( a * b ) # 乘法 輸出：2
print( a / b ) #
今天要來討論 1 + "1" 。
如果當兩個操作數都是數字時，+ 會執行數字相加。例如，1 + 1 結果是 2。
那如果是"1"+"1"，就變成字符串相加變成11。
那我們今天要講的是1 + "1"，答案是11，為甚麼呢?
這是一個類型強制轉換，今天當 + 遇到不一樣的類型時，JavaScrip
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值，那如果我們在迭代中對陣列操作會發生什麼事？
題目來源：https://x.com/_jayphelps/status/1774640511158022335?s=20
(略)，array 是用來將陣列的值進行累加，我們來看看怎麼怎麼達成吧：
Given an integer array nums, a reducer function fn, and an initial value init, return the final result obtained
徵的就是你 🫵 超ㄅㄧㄤˋ 獎品搭配超瞎趴的四大主題，等你踹共啦！還有機會獲得經典的「偉士牌樂高」喔！馬上來參加本次的活動吧！
隨著理財資訊的普及，越來越多台灣人不再將資產侷限於台股，而是將視野拓展到國際市場。特別是美國市場，其豐富的理財選擇，讓不少人開始思考將資金配置於海外市場的可能性。
然而，要參與美國市場並不只是盲目跟隨標的這麼簡單，而是需要策略和方式，尤其對新手而言，除了選股以外還會遇到語言、開戶流程、Ap
給定一個長度為 n 的整數數組 nums 和一個整數target，在 nums 中找到三個整數，使得總和最接近target。傳回三個整數的總和。可以假設每個輸入都有一個解決方案。
一、基本算術運算符號
加法：+
減法：-
乘法：*
除法：/（返回浮點數）
a = 1
b = 2
print( a + b ) # 加法 輸出：3
print( a - b ) # 減法 輸出：-1
print( a * b ) # 乘法 輸出：2
print( a / b ) #
今天要來討論 1 + "1" 。
如果當兩個操作數都是數字時，+ 會執行數字相加。例如，1 + 1 結果是 2。
那如果是"1"+"1"，就變成字符串相加變成11。
那我們今天要講的是1 + "1"，答案是11，為甚麼呢?
這是一個類型強制轉換，今天當 + 遇到不一樣的類型時，JavaScrip
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值，那如果我們在迭代中對陣列操作會發生什麼事？
題目來源：https://x.com/_jayphelps/status/1774640511158022335?s=20
(略)，array 是用來將陣列的值進行累加，我們來看看怎麼怎麼達成吧：
Given an integer array nums, a reducer function fn, and an initial value init, return the final result obtained