arrays साक्षात्कार प्रश्न: तीन सरणियाँ और O(N*N)



algorithm (8)

मान लें कि हमारे पास लंबाई N की तीन सरणियाँ हैं जिनमें मनमाने प्रकार की संख्याएँ हैं। फिर हमें एक नंबर M (एक ही प्रकार का) दिया जाता है और हमारा मिशन प्रत्येक सरणी से तीन संख्याओं A , B और C को चुनना है (दूसरे शब्दों में A को पहले सरणी से उठाया जाना चाहिए, दूसरे से B और तीसरा से B ) इसलिए ए + बी + सी = एम

प्रश्न: क्या हम तीनों संख्याओं को चुन सकते हैं और O (N 2 ) की समय जटिलता के साथ समाप्त हो सकते हैं?

उदाहरण:

सरणी हैं:

1) 6 5 8 3 9 2
2) 1 9 0 4 6 4
3) 7 8 1 5 4 3

और एम हमें दिया गया है 19 है । फिर हमारी पसंद पहली से 8 , दूसरी से 4 और तीसरी से 7 होगी

https://ffff65535.com


1.Store A [i] * B [j] सभी जोड़े के लिए (i, j) हैश डेटा संरचना में आयोजित एक और सरणी डी में। इस चरण की जटिलता ओ (एन * एन) है।

construct a hash named D
for i = 1 to n
    for j = 1 to n
        insert A[i]*B[j] into D

2. सरणी C में प्रत्येक C [i] के लिए, खोजें कि क्या MC [i] D. में मौजूद है। इस चरण की जटिलता O (N) है।

for i = 1 to n
    check if M - C[i] is in D

O (N ^ 2) स्थान की कीमत पर, लेकिन अभी भी O (N ^ 2) समय का उपयोग करते हुए, कोई भी चार सरणियों को संभाल सकता है, पहले दो सरणियों से सभी संभव रकमों की गणना करके, और पिछले दो से सभी संभावित अवशेषों को क्रमबद्ध करता है। सूचियां (रैखिक समय में संभव है क्योंकि वे सभी प्रकार 'लंबी' हैं, जिनके बिट्स की संख्या एन से स्वतंत्र है), और फिर यह देखना कि क्या कोई राशि किसी भी अवशेष के बराबर है।


अन्य समाधान पहले से बेहतर हैं, लेकिन यहाँ मेरा O (n ^ 2) समय और O (n) मेमोरी समाधान वैसे भी है।

सरणी C के सभी तत्वों को हैशटेबल में डालें। (समय जटिलता O (n), अंतरिक्ष O (n)) B (समय जटिलता O (n ^ 2) से A और b से सभी जोड़े (a, b), लीजिए)। प्रत्येक जोड़ी के लिए, जांचें कि क्या M- (a + b) जल्दबाजी में मौजूद है (जटिलता ओ (1) प्रति क्वेरी अपेक्षित)।

तो, समग्र समय जटिलता हे (n ^ 2) है, और हैशटेबल के लिए O (n) की एक अंतरिक्ष जटिलता है।


आप इसे दो सरणियों के साथ समान समस्या के लिए कम कर सकते हैं, जो थोड़े प्रसिद्ध है और इसमें सरल ओ (एन) समाधान है (दोनों सिरों से पुनरावृत्ति शामिल है)।

  1. सभी सरणियों को क्रमबद्ध करें।
  2. A बार पहले सरणी से प्रत्येक संख्या A कोशिश करें।
  3. यह पता करें कि क्या अंतिम दो सरणियाँ हमें संख्या B और C दे सकती हैं, जैसे कि B + C = M - A

चरण 2 और 3 गुणा हमें O (n ^ 2) जटिलता देते हैं।


तीन सरणियों को क्रमबद्ध करें। फिर तीन सूचकांकों को प्रारंभ करें

  1. मैं ए के पहले तत्व की ओर इशारा करता हूं,
  2. j, B के अंतिम तत्व की ओर इशारा करता है और
  3. k, C. के प्रथम तत्व की ओर इशारा करते हुए, जबकि i, j, k अपने संबंधित सरणियों A, B, C की सीमा में हैं

  4. अगर A [i] + B [j] + C [k] == M वापसी

  5. अगर A [i] + B [j] + C [k] <M। इंक्रीमेंट i अगर A [i] <= C [k] अन्यथा इंक्रीमेंट k।

  6. यदि A [i] + B [j] + C [k]> एम। विकृति j।

जो O (n) में चलना चाहिए।


मेरे पास एक उपाय है। सूची के सभी तत्वों को एक हैश तालिका में डालें। यह O (n) समय नहीं लगेगा।

एक बार जब आप पूरा हो जाता है, तो आप शेष 2 सरणियों से सभी जोड़े ढूंढते हैं और देखें कि क्या उनका योग हैश तालिका में मौजूद है।

क्योंकि हैश हुकअप स्थिर है हमें कुल में एक द्विघात समय मिलता है।

इस दृष्टिकोण का उपयोग करके आप छँटाई पर समय बचाते हैं।

एक अन्य विचार यह है कि यदि आप प्रत्येक तत्व के अधिकतम आकार को जानते हैं, तो आप बाल्टी प्रकार की भिन्नता का उपयोग कर सकते हैं और इसे नगण्य समय में कर सकते हैं।


यह O (1) स्पेस और O (N 2 ) समय में किया जा सकता है।

पहले एक सरल समस्या को हल करने देता है:
दो सरणियों को देखते हुए A और B प्रत्येक से एक तत्व लेते हैं ताकि उनकी राशि दिए गए नंबर K बराबर हो।

दोनों सरणियों को क्रमबद्ध करें जो O (NlogN) लेता है।
पॉइंटर्स i और j लें ताकि i A के प्रारंभ में इंगित करता i और B के अंत में j इंगित करता i
A[i] + B[j] का योग खोजें और K इसकी तुलना करें

  • अगर A[i] + B[j] == K हमने A[i] और B[j] जोड़ा पाया है।
  • यदि A[i] + B[j] < K , तो हमें योग बढ़ाने की आवश्यकता है, इसलिए वेतन वृद्धि i
  • यदि A[i] + B[j] > K , तो हमें योग घटाना होगा, इसलिए decrement j

छँटाई के बाद जोड़ी खोजने की यह प्रक्रिया O (N) लेती है।

अब मूल समस्या को लेने देता है। हमें एक तीसरा एरे मिला है जिसे अब C कहते हैं।

तो अब एल्गोरिथ्म है:

foreach element x in C
  find a pair A[i], B[j] from A and B such that A[i] + B[j] = K - x
end for

बाहरी लूप N बार चलाता है और प्रत्येक रन के लिए हम पूरे एल्गोरिथ्म ओ (एन 2 ) बनाते हुए एक ओ (एन) ऑपरेशन करते हैं।


सभी 3 सरणियों को क्रमबद्ध करना और बाइनरी खोज का उपयोग करना बेहतर दृष्टिकोण लगता है। एक बार सरणियों को हल करने के बाद, एक निश्चित रूप से रैखिक खोज के बजाय द्विआधारी खोज के लिए जाना चाहिए, जो लॉग (n) के बजाय n लेते हैं।

हैश टेबल भी एक व्यवहार्य विकल्प है।

हैश और सॉर्ट का संयोजन समय को कम कर सकता है लेकिन ओ (एन स्क्वायर) अंतरिक्ष की कीमत पर।





algorithm