'''
Given an integer array, find three numbers whose product is maximum and
output the maximum product.

Example 1:
Input: [1,2,3]
Output: 6
Example 2:
Input: [1,2,3,4]
Output: 24
Note:
The length of the given array will be in range [3,104] and all elements are
in the range [-1000, 1000]. Multiplication of any three numbers in the input
won't exceed the range of 32-bit signed integer.
'''

class Solution(object):
    def maximumProduct(self, nums):
        nums.sort()
        if nums[0]<0 and nums[1]<0 and abs(nums[1])>=nums[-2]:
            res=nums[0]*nums[1]*nums[-1]
        else:
            res=nums[-1]*nums[-2]*nums[-3]
        return res

मेरा विचार है कि यदि सबसे छोटी 2 ऋणात्मक संख्याओं का निरपेक्ष मान बड़ा है तो दूसरा सबसे बड़ा धनात्मक है, उन ऋणात्मक संख्याओं का उपयोग कैल्क में किया जाना चाहिए। अन्यथा, सबसे बड़े 3 अंकों का गुणनफल होना चाहिए। क्या कोई कृपया देख सकता है और देख सकता है कि तर्क कहां गलत है?

1
dz99194n 30 जून 2017, 19:27

2 जवाब

यहां तीन संभावनाएं हैं:

  1. तीन सबसे बड़ी सकारात्मक संख्याओं का गुणनफल,
  2. दो सबसे छोटी ऋणात्मक संख्याओं के साथ सबसे बड़ी धनात्मक संख्या का गुणनफल,
  3. तीन सबसे बड़ी गैर-धनात्मक संख्याओं का गुणनफल, यदि सूची में कोई धनात्मक संख्या नहीं है। उदाहरण के लिए, [-5, -4, -3, -2, -1] का उत्तर -3 * -2 * -1 = -6 है।

आप संभावना #3 की जांच नहीं करते हैं, इसलिए आपकी दिनचर्या कभी-कभी विफल हो जाएगी।

साथ ही, #1 और #2 के बीच अंतर करने के लिए आप जांचते हैं कि क्या दो सबसे छोटी ऋणात्मक संख्याओं का गुणनफल (nums[0] * nums[1] यदि वे दोनों ऋणात्मक हैं) दूसरी और तीसरी सबसे बड़ी संख्याओं के गुणनफल से बड़ा है (nums[-3] * nums[-2] अगर वे दोनों सकारात्मक हैं)। बेशक आपको यह जाँचने की ज़रूरत है कि तीन सकारात्मक मान हैं, आदि। आपको किनारे के मामले से भी सावधान रहने की ज़रूरत है जहाँ एक या अधिक दिलचस्प मान शून्य हैं।

ध्यान दें कि आप मेरी तीनों संभावनाओं को केवल इस तक कम कर सकते हैं:

nums.sort()
return max(nums[-3] * nums[-2] * nums[-1], nums[0] * nums[1] * nums[-1])

आप सरणी में दो सबसे छोटे और तीन सबसे बड़े मानों को खोजने के साथ sort() को बदलकर एल्गोरिदम की समग्र समय जटिलता को कम कर सकते हैं, लेकिन आपके सरणी आकार के साथ अधिकतम 104 जो यहां चिंता का विषय नहीं है।

0
Rory Daulton 30 जून 2017, 19:54

हो सकता है कि itertools.combination() का उपयोग तीनों संभावित संयोजनों को उत्पन्न करने के लिए करें और फिर प्रत्येक संयोजन के उत्पाद की जांच करें।

import itertools

def prod(iterable): #use this funct as the built-in sum()
    x = 1
    for item in iterable:
        x *= item
    return x

comb = list(itertools.combinations(array, 3))
results= []
for item in comb:
    results.append(prod(item))
print(max(results))
0
Ivan Castro 30 जून 2017, 20:28