यह एक साक्षात्कार प्रश्न है, और समस्या का विवरण इस प्रकार है:

2n सीटों वाली एक पंक्ति में n जोड़े बैठे हैं। सभी को अपने साथी के बगल में बैठाने के लिए न्यूनतम संख्या में स्वैप खोजें। उदाहरण के लिए, 0 और 1 युगल हैं, और 2 और 3 युगल हैं। मूल रूप से वे इस क्रम में एक पंक्ति में बैठे हैं: [2, 0, 1, 3]। स्वैप की न्यूनतम संख्या 1 है, उदाहरण के लिए 2 को 1 के साथ स्वैप करना।

मुझे पता है कि इस समस्या का एक लालची समाधान है। आपको बस सरणी को बाएं से दाएं स्कैन करने की आवश्यकता है। हर बार जब आप एक बेजोड़ जोड़ी देखते हैं, तो आप जोड़ी के पहले व्यक्ति को उसकी सही स्थिति में बदल देते हैं। उदाहरण के लिए, उपरोक्त उदाहरण में जोड़ी [2, 0] के लिए, आप सीधे 2 को 1 से स्वैप करेंगे। 0 को 3 के साथ स्वैप करने का प्रयास करने की कोई आवश्यकता नहीं है।

लेकिन मैं वास्तव में यह नहीं समझता कि यह क्यों काम करता है। मैंने जो सबूत देखे उनमें से एक ऐसा कुछ था:

एक साधारण उदाहरण पर विचार करें: 7 1 4 6 2 3 0 5. पहले चरण में हमारे पास पहले जोड़े से मेल खाने के लिए दो विकल्प हैं: 7 को 0 से स्वैप करें, या 1 को 6 से स्वैप करें, फिर हमें 0 1 4 6 2 3 7 5 या 7 6 4 1 2 3 0 5. ध्यान दें कि पहले जोड़े की कोई और गिनती न हो। बाद के भाग के लिए यह 4 X 2 3 Y 5 (X=6 Y=7 या X=1 Y=0) से बना है। चूंकि अलग-अलग जोड़े असंबंधित हैं, हमें परवाह नहीं है कि एक्स वाई 6 7 जोड़ी या 0 1 जोड़ी है। वे समकक्ष हैं! इस प्रकार इसका मतलब है कि हमारी पसंद की कोई गिनती नहीं है।

मुझे लगता है कि यह बहुत ही उचित है लेकिन पर्याप्त नहीं है। मेरी राय में हमें यह साबित करना होगा कि एक्स और वाई सभी संभावित मामलों में जोड़े हैं और नहीं जानते कि कैसे। क्या कोई संकेत दे सकता है? धन्यवाद!

1
Patrick 1 मार्च 2020, 08:05
क्या आप अपने द्वारा पढ़े गए प्रमाणों में से किसी एक का लिंक प्रदान कर सकते हैं?
 – 
Scratte
2 मार्च 2020, 21:09
लिंक यहाँ है: noreferrer">leetcode.com/problems/couples-holding-hands/discuss/113359/…। मैंने यहां यह सब काफी कॉपी किया है।
 – 
Patrick
3 मार्च 2020, 01:33

3 जवाब

मैंने समस्या को 3 उदाहरणों में विभाजित किया है। A एक जोड़ी हैं और इसलिए B सभी उदाहरणों में हैं। ध्यान दें कि सभी उदाहरणों में एक मैच के लिए आवश्यक है कि तत्व आसन्न हों और पहला तत्व एक इंडेक्स पर कब्जा कर लेता है जो index%2 = 0 को संतुष्ट करता है। इस तरह दिखने वाली एक सरणी [X A1 A2 ...] इस शर्त को पूरा नहीं करती है, हालांकि यह [X Y A1 A2 ...] करती है। उदाहरण भी बाईं ओर बिल्कुल नहीं देखते हैं, क्योंकि नीचे A2 के बाईं ओर देखना A1 के दाईं ओर देखने के समान है।

पहला उदाहरण

दो बेजोड़ जोड़ियों के बीच तत्वों की संख्या सम है:

A1 B1 ..2k.. A2 B2 .. किसी भी संख्या के लिए k in {0, 1, 2, ..} मतलब A1 B1 A2 B2 .. एक और मामला है।

दोनों का एक स्वैप में मिलान किया जा सकता है:

A1 A2 ..2k.. B1 B2 .. या B2 B1 ..2k.. A2 A1 ..

आदेश महत्वपूर्ण नहीं है, इसलिए इससे कोई फर्क नहीं पड़ता कि कौन सी जोड़ी पहले है। एक बार जोड़ियों का मिलान हो जाने के बाद, दोनों में से किसी को भी शामिल करते हुए कोई और अदला-बदली नहीं होगी। A1 के आधार पर A2 खोजने पर B1 के आधार पर B2 खोजने के समान ही स्वैप का परिणाम होगा।

दूसरा उदाहरण

दो जोड़े के बीच तत्वों की एक विषम संख्या है (2k + तत्व C):

A1 B1 ..2k.. C A2 B2 D .. (A1 B1 ..2k.. C B2 A2 D .. समान है)

दोनों का एक स्वैप में मिलान नहीं किया जा सकता है, लेकिन पहले की तरह इससे कोई फर्क नहीं पड़ता कि कौन सी जोड़ी पहले है और न ही मिलान जोड़ी शुरुआत में या सरणी के मध्य भाग में है, इसलिए ये सभी संभावित स्वैप समान रूप से मान्य हैं, और इनमें से कोई भी नहीं वे बाद में और अधिक स्वैप बनाते हैं:

A1 A2 ..2k .. C B1 B2 D .. या B2 B1 ..2k.. C A2 A1 D .. ध्यान दें कि अंतिम जोड़ी का मिलान नहीं है

C B1 ..2k.. A1 A2 B2 D .. या A1 D ..2k.. C A2 B2 B1 .. यहां हम पहली जोड़ी का मिलान नहीं कर रहे हैं।

इसके बारे में महत्वपूर्ण बात यह है कि प्रत्येक मामले में, केवल एक जोड़ी का मिलान किया जाता है और उस जोड़ी के किसी भी तत्व को फिर से बदलने की आवश्यकता नहीं होगी। शेष गैर-मिलान युग्म का परिणाम इनमें से एक है:

..2k.. C B1 B2 D ..
..2k.. C A2 A1 D ..
       C B1 ..2k.. B2 D ..
       A1 D ..2k.. C A2 ..

शेष A या B के मिलान के लिए आवश्यक स्वैप के संदर्भ में वे स्पष्ट रूप से समकक्ष हैं।

तीसरा उदाहरण

यह तार्किक रूप से दूसरे के समान है। B1/A2 और A2/B2 दोनों के बीच कितने भी तत्व हो सकते हैं। कोई फर्क नहीं पड़ता कि कैसे तत्वों की अदला-बदली की जाती है, केवल एक जोड़ी का मिलान किया जा सकता है। m1 और m2 तत्वों की मनमानी संख्या है। ध्यान दें कि तत्व X और Y केवल B2 के आसपास के तत्व हैं, और उनका उपयोग केवल उदाहरण को स्पष्ट करने के लिए किया जाता है:

A1 B1 ..m1.. A2 ..m2.. X B2 Y .. (A1 B1 ..m1.. B2 ..m2.. X A2 Y .. समान है)

फिर से दोनों जोड़ियों का एक स्वैप में मिलान नहीं किया जा सकता है, लेकिन यह महत्वपूर्ण नहीं है कि किस जोड़ी का मिलान किया गया है, या मिलान की जोड़ी की स्थिति कहां है:

A1 A2 ..m1.. B1 ..m2.. X B2 Y .. या B2 B1 ..m1.. A2 ..m2.. X A1 Y .. ध्यान दें कि अंतिम जोड़ी का मिलान नहीं है

A1 X ..m1.. A2 ..m2-1.. B1 B2 Y .. या A1 Y ..m1.. A2 ..m2.. X B2 B1.. B2 की स्थिति पर निर्भर करता है। यहां हम पहली जोड़ी का मिलान नहीं कर रहे हैं।

A2 के आस-पास युग्म का मिलान करना समतुल्य है, लेकिन छोड़ा गया है।

दूसरे उदाहरण की तरह, एक स्वैप शुरुआत में या सरणी के बीच में एक जोड़ी से मेल खा सकता है, लेकिन कोई भी विकल्प नहीं बदलता है कि केवल एक जोड़ी का मिलान किया जाता है। न ही यह बेजोड़ जोड़ियों की शेष राशि को बदलता है।

एक छोटा सा विश्लेषण

यह ध्यान में रखते हुए कि मेल खाने वाले जोड़े बेजोड़/समस्या जोड़े की सूची से बाहर हो जाते हैं, बेजोड़ जोड़े की सूची प्रत्येक स्वैप के लिए या तो एक कम या दो कम जोड़े हैं। चूंकि यह महत्वपूर्ण नहीं है कि कौन सी जोड़ी समस्या से बाहर हो जाती है, यह पहला भी हो सकता है। उस स्थिति में हम मान सकते हैं कि कर्सर/वर्तमान अनुक्रमणिका के बाईं ओर जोड़े सभी मेल खाते हैं। और यह कि हमें केवल पहली जोड़ी से मिलान करने की आवश्यकता है, जब तक कि यह पहले से ही संयोग से मेल नहीं खाती है और कर्सर को सही तरीके से स्थानांतरित किया जाता है।

यह और भी स्पष्ट हो जाता है यदि उपरोक्त उदाहरणों को पहले की बजाय दूसरी बेजोड़ जोड़ी पर कर्सर के साथ देखा जाए। यह अभी भी कोई फर्क नहीं पड़ता कि आवश्यक कुल स्वैप की मात्रा के लिए कौन से जोड़े की अदला-बदली की जाती है। इसलिए बीच में जोड़ियों को मिलाने की कोशिश करने की कोई जरूरत नहीं है। स्वैप की परिणामी राशि समान है।

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

इष्टतम अदला-बदली

बाद में इसे और अधिक इष्टतम स्वैपिंग के लिए तैयार करने के लिए सरणी को संशोधित करने का कोई तरीका नहीं है। या तो एक स्वैप एक या दो जोड़े से मेल खाएगा, या इसे बिना किसी मैच के स्वैप के रूप में गिना जाएगा:

इसे देख रहे हैं: A1 B1 ..2k.. C B2 ... A2 ...

इष्टतम स्वैप की तैयारी के लिए स्वैप करें:

  A1 B1 ..2k.. A2 B2 ... C ...  no matches
  A1 A2 ..2k.. B1 B2 ... C ...  two in one

लालची अदला-बदली:

  B2 B1 ..2k.. C A1 ... A2 ... one
  B2 B1 ..2k.. A2 A1 ... C ... one

बेमेल जोड़े

पहले से मेल खाने वाले जोड़े बेजोड़ नहीं बनेंगे क्योंकि इसके लिए इसकी आवश्यकता होगी:

A1 B1 ..2k.. C A2 B2 D .. के लिए

  • C, A1 या . के समान है
  • D, B1 के समान है

जिनमें से कोई भी असंभव है।

इसी तरह A1 B1 ..m1.. (Z) A2 (V) ..m2.. X B2 Y .. के साथ

या यह आवश्यक होगा कि मिलान किए गए जोड़े को सरणी के अंदर एक (या किसी भी विषम संख्या) अनुक्रमणिका में स्थानांतरित कर दिया जाए। यह भी संभव नहीं है, क्योंकि हम हमेशा स्वैप करते हैं, इसलिए सरणी तत्वों को बिल्कुल भी स्थानांतरित नहीं किया जा रहा है।

2
Scratte 3 मार्च 2020, 16:05

[स्पष्टता के लिए संपादित 4-मार्च-2020।]

एक अदला-बदली करने का कोई मतलब नहीं है जो (कम से कम) एक जोड़े को एक साथ नहीं रखता है। ऐसा करने के लिए स्वैप काउंट में 1 जोड़ दिया जाएगा और हमें समान संख्या में अनपेक्षित जोड़ों के साथ छोड़ दिया जाएगा।

इसलिए, हर बार जब हम अदला-बदली करते हैं, तो हम अधिकतम n-1 जोड़ों को छोड़कर एक जोड़े को एक साथ रख देते हैं। प्रक्रिया को दोहराते हुए हम 1 जोड़ी के साथ समाप्त होते हैं, जो तब तक एक युगल होना चाहिए। तो, सबसे खराब स्थिति n-1 स्वैप होनी चाहिए।

जाहिर है, हम उन जोड़ों को नज़रअंदाज़ कर सकते हैं जो पहले से साथ हैं।

स्पष्ट रूप से, जहां हमारे पास दो जोड़े हैं a:B b:A, एक स्वैप दो जोड़े a:A b:B बनाएगा।

और अगर हमारे पास m जोड़े हैं a:Q b:A c:B ... q:P -- जहां m जोड़े एक "असंबद्ध उपसमुच्चय" (या चक्र) हैं ) जोड़ों के, m-1 स्वैप उन्हें जोड़ों में डाल देंगे।

तो: स्वैप की न्यूनतम संख्या n - s होने जा रही है जहां s "असंबद्ध उपसमुच्चय" की संख्या है (और एस >= 1)। [बेशक, एक उपसमुच्चय में केवल एक जोड़ा हो सकता है।]

दिलचस्प बात यह है कि स्वैप की संख्या को कम करने के लिए आप कुछ भी चतुर नहीं कर सकते हैं। बशर्ते प्रत्येक अदला-बदली एक जोड़े का निर्माण करे, आप न्यूनतम संख्या करेंगे।

यदि आप प्रत्येक जोड़े को ऊंचाई के क्रम में व्यवस्थित करना चाहते हैं, तो चीजें अधिक दिलचस्प हो भी सकती हैं और नहीं भी।


एफडब्ल्यूआईडब्ल्यू: यह दर्शाने के बाद कि आप n जोड़ों के प्रत्येक असंबद्ध सेट के लिए n-1 स्वैप से बेहतर नहीं कर सकते हैं, तब चाल O से बचने की है >(n^2) प्रत्येक स्वैप के लिए खोजें। यह एक वेक्टर को प्रति व्यक्ति एक प्रविष्टि के साथ रखकर अपेक्षाकृत सरलता से किया जा सकता है, जहां वे वर्तमान में बैठे हैं। फिर एक स्कैन में आप प्रत्येक व्यक्ति को उठाते हैं और यदि आप जानते हैं कि उनका साथी कहां बैठा है, तो जोड़ी बनाने के लिए नीचे स्वैप करें, और स्वैप किए गए व्यक्ति के स्थान को अपडेट करें।

1
Chris Hall 4 मार्च 2020, 13:25
यह ध्यान देने योग्य है कि "असंबद्ध उपसमुच्चय" हमेशा चक्र होते हैं; यह अनिवार्य रूप से क्रमचय का चक्र अपघटन है, और स्वैप की न्यूनतम संख्या इस पर निर्भर करती है चक्रों की लंबाई।
 – 
kaya3
3 मार्च 2020, 16:54

मैं प्रत्येक even तैनात सदस्य की अदला-बदली करूंगा, अगर वह अपने साथी के अलावा नहीं बैठता है।

यहां तक ​​​​कि तैनात का मतलब है कि सरणी अनुक्रमित 1, 3, 5 और इसी तरह।

जोड़े [सम, विषम] जोड़ी हैं। उदाहरण के लिए [0, 1], [2, 3], [4, 5] और इसी तरह।

लूप ऐसा होगा:

for(i=1; i<n*2; i+=2)  //  when n = # of couples.

अब, हम i-th और (i-1)-th अनुक्रमणिका सदस्य की जांच करेंगे। यदि वे युगल नहीं हैं, तो हम (i-1)-th सदस्य के साथी की तलाश करेंगे और एक बार हमारे पास हो जाने पर, हमें इसे i-th सदस्य के साथ बदल देना चाहिए।

उदाहरण के लिए, मान लीजिए i=1 पर, हमें 6 मिला, अब यदि (i-1)-th तत्व 7 है तो वे एक युग्म बनाते हैं (यदि (i-1)-th तत्व 5 है तो [5, 6] युगल नहीं है। ) और हमें किसी स्वैप की आवश्यकता नहीं है, अन्यथा हमें (i-1)-th तत्व के भागीदार की तलाश करनी चाहिए और i-th तत्व के साथ अदला-बदली करनी चाहिए। तो, (i-1)-th और i-th एक जोड़े का निर्माण करेंगे।

यह सुनिश्चित करता है कि हमें कुल सदस्यों में से केवल आधे की जांच करने की आवश्यकता है, अर्थात n

और, किसी भी गैर-मिलान जोड़े के लिए, हमें i-th स्थिति से शेष सरणी तक एक रैखिक खोज की आवश्यकता है। जो O(2n) है, अंततः O(n) है।

तो, समग्र तकनीक जटिलता ओ (एन ^ 2) होगी।

सबसे खराब स्थिति में, न्यूनतम स्वैप n-1 होगा। (यह भी अधिकतम है)।

बहुत सीधा। अगर आपको कोड करने में मदद चाहिए, तो हमें बताएं।

0
User_67128 2 मार्च 2020, 18:11
आश्चर्य है कि सरणी को सॉर्ट करने से बेहतर प्रदर्शन नहीं मिलेगा। कुछ सॉर्टिंग एल्गोरिदम में O(nlogn) होते हैं। बेशक यह जरूरी नहीं कि स्वैप की न्यूनतम राशि भी प्राप्त करे।
 – 
Scratte
2 मार्च 2020, 15:45
जब संभव हो तो छँटाई न्यूनतम स्वैप सुनिश्चित नहीं करती है, प्रश्न इसके बारे में रुचि रखता है।
 – 
User_67128
2 मार्च 2020, 15:51
धन्यवाद! मुझे लगता है कि मुझे समझ में नहीं आता है कि हमें केवल यहां तक ​​कि तैनात सदस्य को स्वैप करने का प्रयास करने की आवश्यकता क्यों है। उदाहरण के लिए, [2, 0, 1, 3] में पहली जोड़ी के लिए, हम या तो 1 के साथ 2 को स्वैप कर सकते हैं या 0 के साथ 3। जैसा कि आपने उल्लेख किया है कि हमें केवल 2 को 1 के साथ स्वैप करने की आवश्यकता है, लेकिन उस स्वैपिंग को कैसे साबित करें < i>विषम तैनात सदस्य कम स्वैप के साथ समाधान प्रदान नहीं करेगा?
 – 
Patrick
3 मार्च 2020, 01:36
अगले नंबर की जांच करने से पहले आपको 2 को आगे नहीं बढ़ाना चाहिए, यह 3 मैच हो सकता है। इसलिए, हम उम्मीद कर रहे हैं कि अगला नंबर एक मैच होगा, जब ऐसा नहीं होता है, तो हम उस नंबर को सही नंबर से बदल देंगे।
 – 
User_67128
3 मार्च 2020, 03:46