क्या कोई कृपया उपरोक्त प्रश्न के साथ मेरी मदद कर सकता है। हमें सरणी (a1,a2),(a1,a3),(a1,a4).... में तत्वों के संयोजन को खोजना है, और उन संयोजनों को चुनना है जो शर्त को संतुष्ट करते हैं (ai*aj) <= max (ए) जहां ए सरणी है और संभव संयोजनों की संख्या लौटाएं।

उदाहरण: इनपुट सरणी ए = [१,१,२,४,२] और यह ८ देता है क्योंकि संयोजन हैं: (1,1),(1,2),(1,4),(1,2), (1,2),(1,4),(1,2),(2,2)।

लूप के लिए नेस्टेड का उपयोग करके इसे हल करना आसान है लेकिन यह बहुत समय लेने वाला होगा। (ओ (एन ^ 2))।

अनुभवहीन एल्गोरिथ्म:

array = [1,1,2,4,2]
result = []
for i in range(len(array)):
   for j in range(len(array)):
       if array[i] * array[j] <= max(array):
           if (array[j],array[i]) not in result:
               result.append((array[i],array[j]))
print(len(result))

जब हम ऐसी समस्याओं का सामना करते हैं तो दृष्टिकोण क्या होना चाहिए?

0
Roosh 9 अक्टूबर 2018, 16:11

3 जवाब

सबसे बढ़िया उत्तर

सरणी को सॉर्ट करने के बारे में क्या है, फिर पुनरावृत्त करना: प्रत्येक तत्व के लिए, e, बाइनरी floor(max(A) / e) के निकटतम तत्व को खोजती है जो e से कम या उसके बराबर है। उस अनुक्रमणिका के बाईं ओर तत्वों की संख्या जोड़ें। (यदि कई डुप्लिकेट हैं, तो उनकी गिनती हैश करें, उनमें से केवल दो को क्रमबद्ध सरणी में प्रस्तुत करें, और किसी भी अनुक्रमणिका के बाईं ओर आइटम की सही संख्या वापस करने के लिए उपसर्ग योग का उपयोग करें।)

1 1 2 4 2

1 1 2 2 4
0
  1
    2
      3
        2
0
גלעד ברקן 9 अक्टूबर 2018, 13:49

आपकी समस्या के विवरण को पढ़कर मैं जो समझता हूं वह यह है कि आप उन युग्मों की कुल संख्या ज्ञात करना चाहते हैं जिनका गुणन इन युग्मों के बीच की सीमा में अधिकतम तत्व से कम है अर्थात ai*aj <= max(ai,ai+1,…aj)

थॉमस द्वारा सुझाए गए सरल दृष्टिकोण को समझना आसान है लेकिन यह अभी भी O(n^2)) की समय जटिलता का है। हम समय की जटिलता को कम करके O(n*log^2n) करने के लिए इसे अनुकूलित कर सकते हैं। आइए इसके बारे में विस्तार से चर्चा करते हैं।

सबसे पहले, प्रत्येक इंडेक्स- i से, हम यह पता लगा सकते हैं कि {l, r} किस तत्व में इंडेक्स- i, l से i तक के सभी तत्वों से बड़ा या बराबर होगा। , साथ ही यह i + 1 से r तक के सभी तत्वों से बड़ा है। इसे हिस्टोग्राम डेटा-संरचना

अब, प्रत्येक अनुक्रमणिका-i के लिए, हम ऐसी श्रेणी {l, r} का पता लगाते हैं, और यदि हम दो श्रेणियों में से न्यूनतम लंबाई को पार करना चाहते हैं यानी min( i - l, r - i ) तो कुल मिलाकर हम n*logn सूचकांकों को पार करेंगे समग्र सरणी के लिए। छोटी लंबाई सीमा में यात्रा करते समय, यदि हमें कुछ तत्व x मिलते हैं, तो हमें किसी तरह यह पता लगाना होगा कि अन्य श्रेणी में कितने तत्व मौजूद हैं जैसे कि मान ai / x से कम हैं। इसे O(logn) समय जटिलता में Fenwick Tree डेटा-स्ट्रक्चर के साथ ऑफ़लाइन प्रसंस्करण का उपयोग करके हल किया जा सकता है प्रत्येक क्वेरी के लिए। इसलिए, हम उपरोक्त समस्या को O(n log^2 n) समय जटिलता की समग्र जटिलता के साथ हल कर सकते हैं।

0
BishalG 24 अक्टूबर 2018, 06:47

लूप के लिए नेस्टेड का उपयोग करके इसे हल करना आसान है लेकिन यह बहुत समय लेने वाला होगा। (ओ (एन ^ 2))।

चूंकि where i < j हम इसे आधा कर सकते हैं:

for i in range(len(array)):
  for j in range(i+1, len(array)):
    ...

अब आइए इस भाग से छुटकारा पाएं if (array[j],array[i]) not in result: क्योंकि यह आपके परिणामों को प्रतिबिंबित नहीं करता है: (1,1),(1,2),(1,4),(1,2),(1,2),(1,4),(1,2),(2,2) यहां आपके पास डुप्ली हैं।

अगला महंगा कदम जिससे हम छुटकारा पा सकते हैं, वह है max(array) जो न केवल गलत है (max(ai,ai+1,…aj) का अनुवाद max(array[i:j])) है, बल्कि इसके पूरे खंड को दोहराना है प्रत्येक पुनरावृत्ति में सरणी। चूंकि ऐरे नहीं बदलता है, केवल एक चीज जो इस अधिकतम को बदल सकती है, वह है array[j], वह नया मान जिसे आप संसाधित कर रहे हैं।

आइए इसे एक चर में संग्रहीत करें:

array = [1,1,2,4,2]
result = []

for i in range(len(array)):
  maxValue = array[i]
  for j in range(i+1, len(array)):
    if array[j] > maxValue:
      maxValue = array[j]
    if array[i] * array[j] <= maxValue:
      result.append((array[i], array[j]))

print(len(result))

अभी भी एक भोली एल्गोरिथ्म, लेकिन imo हमने कुछ सुधार किए हैं।

एक और चीज जो हम कर सकते हैं, वह है न केवल maxValue, बल्कि एक pivot = maxValue / array[i] को भी स्टोर करना और इसलिए गुणन को एक साधारण तुलना if array[j] <= pivot: से बदलना। ऐसा इस धारणा के तहत करना कि गुणन को maxValue की तुलना में अधिक बार कहा जाएगा और इसलिए pivot बदल जाता है।

लेकिन चूंकि मैं अजगर में बहुत अनुभवी नहीं हूं, इसलिए मुझे यकीन नहीं है कि इससे अजगर या गीलेर में कोई फर्क पड़ेगा, मैं इसके साथ व्यर्थ सूक्ष्म अनुकूलन के लिए सड़क पर हूं।

0
Thomas 9 अक्टूबर 2018, 15:58