목록에서 두 요소의 최대 곱을 찾는 방법은 무엇입니까?

재미있게 해커 크랭크 대회에서 문제를 시도하고 있었는데,이 질문이 왔습니다. 은 여기,이에 대한 itertools을 사용하는 코드입니다 :목록에서 두 요소의 최대 곱을 찾는 방법은 무엇입니까?

import itertools 

l = [] 

for _ in range(int(input())): 
    l.append(int(input())) 


max = l[0] * l[len(l)-1] 

for a,b in itertools.combinations(l,2): 
    if max < (a*b): 
     max = (a*b) 
print(max)

이 아닌 다른 효율적인 방법들이 있습니까? 내가 액세스 할 수없는 몇 가지 테스트 케이스에서 시간 초과 오류가 발생하므로 (작은 대회로)

출처

2016-09-05 Maverick

사전 계산 'a * b'최대 값이 아닌 경우 몇 가지 지침을 저장합니다. –

@ Jean-FrançoisFabre가 당신을 명확하게 이해하지 못했습니다. 제발 좀 더 자세히 설명해 주시겠습니까? – Maverick

두 개의 가장 큰 개별 요소를 찾아서 곱하면 안됩니까? (또한 음수를 허용하는 경우 두 개의 가장 낮은 음수 요소) – khelwood

다음은 @ User_Targaryen의 논리를 따르는 구현입니다. heapq은 목록에서 2 개의 가장 큰 숫자와 2 개의 가장 작은 숫자를 반환하며, mul operator은이 2 쌍의 숫자의 곱을 반환하고 max은이 2 개의 제품 중 가장 큰 것을 반환합니다.

>>> import heapq 
>>> from operator import mul 
>>> l = [2,40,600,3,-89,-899] 
>>> max(mul(*heapq.nsmallest(2,l)),mul(*heapq.nlargest(2,l))) 
80011 
# -899*-89 = 80011

출처

2016-09-05 11:52:42

이것은 좋은 것이지, 타임 아웃이 아니지만, 하나의 테스트 케이스에서 여전히 실패하고 이유를 알지 못합니다. 만약 누군가가 https://www.hackerrank.com/contests/arraysloops/challenges/arraysloops-4 – Maverick

을 시도하고 싶다면 여기 링크가있다. @Maverick 나는 람다 문법 대신에'mul'을 약간 사용하여 나의 대답을 편집했다. 이걸 읽은 후에 http://stackoverflow.com/questions/2104782/returning-the-product-of-a-list –

당신은'reduce'를 사용할 필요가 없으므로 튜플 압축을 풀어보십시오 :'max (mul (* heapq. nsmallest (2, l)), mul (* heapq.nlargest (2, l)))'. 이 힙 솔루션은 긴 목록의 내 정렬 기반 솔루션보다 빠릅니다. – mhawke

으로 반복 목록을 통해 찾아 다음

최대 양수 (A)

두 번째로 큰 양수 (b)에

최대 음수 (C)

두 번째로 큰 음수 (d)

이제 승산시 최대 값을 확인할 수 있습니다 (). 0 또는 c*d

출처

2016-09-05 11:47:04

상자 밖에서 생각하고, 잘 했어! –

좋은 논리, 나는 heapq 해결책이 있던 응답으로 갔다. 귀하의 답변에 감사드립니다. – Maverick

그냥 목록을 정렬하고 목록에서 목록의 마지막 두 항목 및 제 2 개 항목의 제품의 가장 큰 선택

from operator import mul 

numbers = [10, 20, 1, -11, 100, -12] 
l = sorted(numbers) # or sort in place with numbers.sort() if you don't mind mutating the list 
max_product = max(mul(*l[:2]), mul(*l[-2:]))

이것은 O입니다 (N 로그 n) 솔루션을 제공합니다. 다른 누군가는 heapq 해결책을 제안했는데 몇 천 개가 넘는 임의의 정수보다 긴 목록보다 빠르다는 것을 알았습니다.

출처

2016-09-05 12:19:31 mhawke

해답을 주셔서 감사합니다. 그러나 heapq는 일부 테스트 케이스에 적합하므로 태그를 붙여야했습니다. 나는 당신의 솔루션도 좋아했다. 그것은 더 간단했다. – Maverick

@Maverick : 문제 없습니다. 기본적으로는 동일하지만 heapq는 경우에 따라 약간 더 빠릅니다. – mhawke

목록에서 두 요소의 최대 곱을 찾는 방법은 무엇입니까?

답변

관련 문제