1464. Maximum Product of Two Elements in an Array [배열, 정렬, Heap (Priority Queue)]

설명

정수들의 배열이 주어지면, 당신은 배열의 서로 다른 두 지수 i와 j를 선택할 것이다.

(nums[i]-1)*(nums[j]-1)의 최대값을 반환하라.

 

https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/

입력, 출력

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

문제 해석

• 가장 큰 값과 두 번째로 큰 값을 찾아 값 -1 을 곱한 결과를 리턴

코드 설명

• 순차 탐색

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max1, max2 = nums[:2]
        if max2 > max1:
            max1, max2 = max2, max1
        for n in nums[2:]:
            if n > max1:
                max1, max2 = n, max1
            elif n > max2:
                max2 = n
        return (max1-1) * (max2-1)

• sort 내장 함수

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        nums.sort()
        return (nums[-1]-1) * (nums[-2]-1)

결론

순차 탐색

• 시간 복잡도 O(n)
• 공간 복잡도 O(1)
• 더 효율적인 방법입니다.

sort 내장함수

• 시간 복잡도 O(n log n)
• 공간 복잡도 O(1) 또는 O(n)
• 시간이 더 오래 걸리지만 상대적으로 코드가 더 간단합니다.