दिए गए योग

Question

से कम या उसके बराबर राशि के साथ सरणी में सभी ट्रिपलेट्स को हाल ही में एक साक्षात्कार में एक दोस्त से पूछा गया था और हम सरल ओ (एन) के अलावा किसी भी समाधान के बारे में नहीं जानते हैं।

क्या कुछ बेहतर एल्गोरिदम है? मैं प्रदर्शन O (n के साथ इतने पर अन्य इस तरह की समस्याओं को देखा है लॉग:

प्रश्न एक पूर्णांक सरणी जिसका राशि से कम या दिए गए योग एस

नोट के बराबर है में सभी तीन को मिल रहा है n) लेकिन वे सभी इस समस्या के आसान संस्करण को हल कर रहे थे जैसे कि arr[i] + arr[j] + arr[k] = S या जहां वे केवल यह जांच रहे थे कि ऐसा एक तिहाई मौजूद है या नहीं।

मेरा प्रश्न में arr[] ऐसी है कि arr[i] + arr[j] + arr[k] <= S

Answer 1

बुरी से बुरी हालत asymptotic दृष्टिकोण से, कोई बेहतर एल्गोरिथ्म है के बाद से उत्पादन के आकार संभावित O(n^3) है सब i,j,k पता लगाने के लिए है।

उदा। सरणी संख्या 1 से n होने दें। S = 3n दें। जाहिर है, तीन सरणी तत्वों का कोई सबसेट S से कम होगा और (n choose 3) = O(n^3) सबसेट्स हैं।

हालांकि कुछ तरीकों से आप गैर-खराब मामलों को तेज कर सकते हैं। उदाहरण के लिए, पहले सरणी को सॉर्ट करने का प्रयास करें। आपको कुछ संकेत देना चाहिए।

Answer 2

मुझे एक विचार है, लेकिन मुझे यकीन नहीं है कि यह काम करता है या नहीं।

प्रीप्रोसेस (तत्वों को हटाएं>S) और पहले सरणी को सॉर्ट करें।

उसके बाद, आप arr[i] और arr[j] जहां i < j उठा के बाद, आप कर सकते हैं शेष array[j+1...n] में द्विआधारी खोज S - arr[i] - arr[j]। एक बार जब आप सूचकांक m पर बाइनरी-खोज की, तो kj+1 और m के बीच झूठ बोल सकता है।

मुझे लगता है कि इससे जटिलता कम हो सकती है। तुम क्या सोचते हो?

Answer 3

इसकी जटिलता क्या होगी?

यदि किसी क्रमबद्ध सूची (आरोही) पर लागू किया गया है, तो f बस उन तीनों को सूचीबद्ध करता है जो राशि s से कम या बराबर होती है, एक-एक करके, डुप्लीकेट बनाने या पहले तत्व के पहले स्कैनिंग के बिना स्कैनिंग।

हास्केल कोड:

f []  s result = if length result == 3 then [result] else [] 
f (x:xs) s result 
    | length result == 3 = [result] 
    | x + sum result > s = [] 
    | otherwise   = f xs s (x:result) ++ f xs s result 

आउटपुट:

*Main> length $ f [1..300] 300 [] 
731375 
(5.09 secs, 402637784 bytes) 

*Main> f [1..10] 13 [] 
[[3,2,1],[4,2,1],[5,2,1],[6,2,1],[7,2,1],[8,2,1],[9,2,1],[10,2,1],[4,3,1] 
,[5,3,1],[6,3,1],[7,3,1],[8,3,1],[9,3,1],[5,4,1],[6,4,1],[7,4,1],[8,4,1] 
,[6,5,1],[7,5,1],[4,3,2],[5,3,2],[6,3,2],[7,3,2],[8,3,2],[5,4,2],[6,4,2] 
,[7,4,2],[6,5,2],[5,4,3],[6,4,3]] 

Answer 4

यह हे में हल किया जा सकता (एन^2) जटिलता।

पहले प्रकार संख्या -> ओ (nlog (एन))

अब सामने से शुरू, एक समय में एक नंबर को ठीक। अब समस्या क्रमबद्ध सरणी में 2 संख्याओं को खोजने के लिए कम हो जाती है जिसका योग < = दिया गया योग है।2 पॉइंटर्स का उपयोग करना, शुरुआत से एक और अंत में से एक, इसे ओ (एन) में हल किया जा सकता है। तो समग्र जटिलता ओ (एन 2)

Answer 5

मुझे विश्वास है कि इस एल्गोरिदम को ओ (एन^2) में चाल चलनी चाहिए। हालांकि आपको सरणी को पहले से सॉर्ट करना चाहिए।

अनिवार्य रूप से, मुझे बस सभी संभावित ट्रिपलेट मिल रहे हैं जहां पहली अनुक्रमणिका मैं शून्य हूं और अगली अनुक्रमणिका शेष सूचकांक (के) के माध्यम से एक्स के बराबर या उसके बराबर सभी रकम के लिए खोज कर जा रही है (या आपके मामले में एस)। उसके बाद, मैं 1 से जे बढ़ाता हूं और प्रक्रिया दोहराता हूं। एक बार जब सरणी के अंत में आता है, तो मैं प्रक्रिया को अपने + 1 के साथ शुरू करता हूं और तब तक चलता रहता हूं जब तक कि मैं दूसरे को अंतिम सूचकांक मान के बराबर नहीं करता (क्योंकि उस बिंदु पर कोई संभावित तीन गुना शेष नहीं है)।

अजगर कोड

def numTriplets(a,x): 
    if len(a) < 3: 
     return None 
    i = 0 
    j = 1 
    triplets = [] 
    while True: 
     for k in range(j+1,len(a)): 
     if a[i] + a[j] + a[k] <= x: 
      triplets.append([i,j,k]) 
     j += 1 
     if j == len(a) - 1: 
     i += 1 
     j = i + 1 
     if i == len(a) - 2: 
     return triplets