2015-11-28 5 views
5

बना सकती है मेरे पास एन पूर्णांक हैं, उदाहरण के लिए 3, 1, 4, 5, 2, 8, 7. कुछ डुप्लीकेट हो सकते हैं। मैं इस क्रम को संगत अनुक्रमों में विभाजित करना चाहता हूं जैसे कि हम उनसे कम घटते अनुक्रम बना सकते हैं। कम से कम कटौती की गणना कैसे करें? ऊपर वर्णित उदाहरण के लिए, उत्तर 6 है, क्योंकि हम इस अनुक्रम को {3}, {1}, {4, 5}, {2}, {7}, {8} में विभाजित कर सकते हैं और फिर {1, 2 , 3, 4, 5, 7, 8}। ऐसा करने का सबसे तेज़ तरीका क्या है?टुकड़े टुकड़े में विभाजन अनुक्रम में कटौती की न्यूनतम संख्या जो एक गैर-घटते अनुक्रम

क्या कोई यह जानता है कि इसे हल करने का तरीका यह है कि कुछ संख्या बराबर हो सकती है?

+0

ग्राफ-सिद्धांत या मल्टीसेट के रूप में टैग क्यों किया गया है? यदि आप सोचते हैं, उदाहरण के लिए, वह ग्राफ यहां उपयोगी हो सकते हैं, तो कृपया हमारे निष्कर्ष हमारे साथ साझा करें। जैसा कि यह खड़ा है, आपका प्रश्न कोई प्रयास या शोध नहीं दिखाता है –

+0

मैंने इसे ग्राफ सिद्धांत के रूप में टैग किया क्योंकि कई कठोर समस्याएं जो ग्राफ के साथ चिंतित नहीं दिखती हैं, ग्राफ सिद्धांत में समाधान हैं। मुझे नहीं पता कि इस समस्या को कैसे हल किया जाए। – user128409235

+0

@ पॉल नहीं यह नहीं है। इस उदाहरण पर एक नज़र डालें: 3, 1, 4, 5, 2, 8, 7. आपका एल्गोरिदम इसे {3}, {1, 4, 5}, {2, 8}, {7} में विभाजित करेगा, लेकिन हम इन टुकड़ों में से एक कम घटते seqeunce नहीं कर सकते हैं। – user128409235

उत्तर

2

मैं मानों को कम करने वाले बिंदुओं पर गैर-घटते खंडों में सरणी काट दूंगा, और फिर इन खंडों को एक (एकल) विलय चरण में इनपुट के रूप में उपयोग करें - जैसा कि एक समान खंड में रखते हुए - एक ही सेगमेंट में रखते हुए, जहां संबंधों के मामले में, संभव है। कटौती के लिए अतिरिक्त स्थान बनाएं जब आपको एक सेगमेंट में दूसरे से स्विच करना होगा।

आउटपुट सॉर्ट किया गया है, इसलिए यह नौकरी करने के लिए पर्याप्त कटौती करता है। कट्स उन बिंदुओं पर उत्पादित होते हैं जहां अनुक्रम घटता है, या उन बिंदुओं पर जहां एक अंतर बनाया जाना चाहिए क्योंकि मूल अनुक्रम किसी अन्य स्थान पर मौजूद होता है - इसलिए इन सभी कटों के बिना कोई अनुक्रम सॉर्ट किए गए क्रम में पुन: व्यवस्थित नहीं किया जा सकता है।

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

1

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

हम फेनविक पेड़ का उपयोग कर O(n * log n) समय और O(n) स्थान पर क्रमपरिवर्तन विवर्तन वेक्टर की गणना कर सकते हैं। उसी संख्या वाले वेक्टर के निरंतर खंड उन वर्गों का प्रतिनिधित्व कर सकते हैं जिन्हें कटौती की आवश्यकता नहीं है। दुर्भाग्य से, वे भी झूठे सकारात्मक लौट सकते हैं, जैसे,

Array: {8,1,4,5,7,6,3} 
Vector: 0,1,1,1,1,2,5 

जहां 6 और 3 मतलब अनुक्रम, [1,4,5,7] में कटौती। इसका मुकाबला करने के लिए, हम प्रत्येक तत्व के बाद छोटे तत्वों की संख्या का प्रतिनिधित्व करते हुए एक दूसरा उलटा वेक्टर लेते हैं। दोनों वैक्टरों में समानांतर खंडों को काटने की आवश्यकता नहीं है:

Array: {8,1,4,5,7,6,3,0} 
Vector: 0,1,1,1,1,2,5,7 // # larger preceding 
Vector: 7,1,2,2,3,2,1,0 // # smaller following 
      |---| // not cut 

Array: {3,1,4,5,2,8,7} 
Vectors: 0,1,0,0,3,0,1 
      2,0,1,1,0,1,0 
      |---| // not cut 

Array: {3,1,2,4} 
Vectors: 0,1,1,0 
      2,0,0,0 
      |---| // not cut 
+0

क्या होगा यदि कुछ संख्या बराबर हो सकती है? उदाहरण के लिए 8, 1, 4, 5, 3, 7, 6, 3 – user128409235

+0

3, 1, 3 के लिए यह गलत जवाब देगा 2. – user128409235

+0

@ user128409235 आपकी टिप्पणियों के लिए धन्यवाद। मैंने आपके दो उदाहरणों को मेरे उत्तर के अंत में डुप्लिकेट के साथ जोड़ा। –

संबंधित मुद्दे