निम्न समस्या एल्गोरिदम की समस्या (समस्या 653):

आपको संख्याओं का एक n x 2 मैट्रिक्स दिया गया है। एक ओ (एन लॉग एन) एल्गोरिदम खोजें जो सरणी में पंक्तियों को इस तरह से क्रमबद्ध करता है कि सरणी के किसी भी कॉलम में n.

मुझे यकीन नहीं है कि इसे कैसे हल किया जाए। मुझे लगता है कि यह किसी प्रकार के विभाजन और जीत की पुनरावृत्ति का उपयोग कर सकता है, लेकिन मुझे एक नहीं मिल रहा है।

क्या किसी के पास कोई विचार है कि इसे कैसे हल किया जाए?

6
GEP 31 अगस्त 2011, 00:28
N के वर्ग रूट से लंबा है?
 – 
andrew cooke
31 अगस्त 2011, 00:30
1
यह 'एल्गोरिदम पर समस्याएं' पुस्तक में 653 समस्या है।
 – 
GEP
31 अगस्त 2011, 00:36
पुस्तक के पीडीएफ का लिंक यहां दिया गया है:larc.unt.edu/ian /books/free/license.html
 – 
GEP
31 अगस्त 2011, 00:38
मुझे लगता है कि इसका विभाजन और जीत मुझे संदेह है कि विलय के कदम में कुछ गणित भी शामिल है।
 – 
GEP
31 अगस्त 2011, 01:03

1 उत्तर

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

यहाँ मेरा समाधान है।

1) पहले तत्व के अनुसार पंक्तियों को सबसे बड़े से निम्नतम तक क्रमबद्ध करें।

1 6    5 1
3 3 -\ 3 3
2 4 -/ 2 4
5 1    1 6

2) इसे n⌉ के समूहों में विभाजित करें, और जो बचा है (और नहीं ⌈√n⌉ समूह)

5 1    5 1
3 3 -\ 3 3
2 4 -/ 
1 6    2 4
       1 6

3) प्रत्येक समूह में पंक्तियों को दूसरे तत्व के अनुसार सबसे बड़े से निम्नतम तक क्रमबद्ध करें

5 1    3 3
3 3    5 1
    -> 
2 4    1 6
1 6    2 4

सटीकता का प्रमाण:

कॉलम 1 में बढ़ते क्रम केवल एकल समूह में हो सकते हैं (आकार <= n⌉ है),

कॉलम 2 में बढ़ते क्रम के कोई 2 तत्व एक ही समूह में नहीं हैं (⌈√n⌉ समूहों से अधिक नहीं)

5
kilotaras 31 अगस्त 2011, 13:50
2
आह, इतना आसान। मैंने ऐसा क्यों नहीं देखा? बहुत बढ़िया।
 – 
flight
31 अगस्त 2011, 16:18
1
लगभग 5 मिनट। मैंने यह सोचकर शुरुआत की कि मैं 1xn समस्या (एक कॉलम) को कैसे हल करूं।
 – 
kilotaras
31 अगस्त 2011, 22:02
पेंसिल और कागज हमेशा मदद करते हैं।
 – 
kilotaras
1 सितंबर 2011, 14:38