मैं कैसे कुशलता से निर्धारित कर सकता हूं कि दो सूचियों में तत्वों का आदेश दिया गया है या नहीं?

Question

मेरे पास एक ही तत्व प्रकार की दो आदेशित सूचियां हैं, प्रत्येक सूची प्रत्येक मान के अधिकांश तत्व (इनट्स और अद्वितीय संख्याएं कहती है) पर है, लेकिन अन्यथा कोई प्रतिबंध नहीं है (कोई दूसरे का सबसेट हो सकता है, वे पूरी तरह से हो सकते हैं विसंगत, या कुछ तत्व साझा करें लेकिन दूसरों को नहीं)।

मैं कुशलतापूर्वक यह निर्धारित कैसे कर सकता हूं कि ए बी के मुकाबले अलग-अलग तरीके से किसी भी दो आइटम का ऑर्डर कर रहा है या नहीं? उदाहरण के लिए, यदि ए में आइटम 1, 2, 10 और बी आइटम 2, 10, 1 है, तो संपत्ति 10 से पहले 1 सूचियों के रूप में नहीं रखी जाएगी लेकिन बी इसे 10 के बाद सूचीबद्ध करता है। 1, 2, 10 बनाम 2, 10 , 5 पूरी तरह मान्य होगा हालांकि ए ने कभी भी 5 का उल्लेख नहीं किया है, मैं दोनों सूचियों द्वारा साझा किए गए किसी दिए गए सॉर्टिंग नियम पर भरोसा नहीं कर सकता।

Answer 1

आप निम्नानुसार ओ (एन) प्राप्त कर सकते हैं। सबसे पहले, हैशिंग का उपयोग करके दो सेटों के चौराहे को ढूंढें। दूसरा, परीक्षण करें कि क्या ए और बी समान हैं यदि आप केवल छेड़छाड़ के तत्वों पर विचार करते हैं।

for i in 1 .. length(A): 
    Apos[i] = (A, i) 
sortedApos = sort(Apos[] by first element of each pair) 

for i in 1 .. length(B): 
    Bpos[i] = (B, i) 
sortedBpos = sort(Bpos[] by first element of each pair) 

अब एक मानक सूची मर्ज कि रिकॉर्ड का उपयोग कर आम में उन तत्वों को खोजने:

Answer 2

मेरे दृष्टिकोण पहले A और B की क्रमबद्ध प्रतियां जो भी मूल सूचियों में तत्वों की स्थिति को रिकॉर्ड बनाने के लिए किया जाएगा A और साझा तत्वों की B दोनों में पदों:

i = 1 
j = 1 
shared = [] 
while i <= length(A) && j <= length(B) 
    if sortedApos[i][1] < sortedBpos[j][1] 
     ++i 
    else if sortedApos[i][1] > sortedBpos[j][1] 
     ++j 
    else // They're equal 
     append(shared, (sortedApos[i][2], sortedBpos[j][2])) 
     ++i 
     ++j 

अंत में, प्रकार अपना पहला तत्व द्वारा shared (में स्थिति 0) और जांचें कि इसके सभी दूसरे तत्व (B में स्थितियां) बढ़ रही हैं। यह A को आम तत्वों iff मामले हो जाएगा और B उसी क्रम में दिखाई देते हैं:

sortedShared = sort(shared[] by first element of each pair) 
for i = 2 .. length(sortedShared) 
    if sortedShared[i][2] < sortedShared[i-1][2] 
     return DIFFERENT 

return SAME 

समय जटिलता: 2 * (ओ (एन) + O (nlog एन)) + O (एन) + O (nlog n) + O (n) = ओ (nlog n)।

Answer 3

सामान्य दृष्टिकोण: सभी मानों और उनकी स्थिति को बी में हेश मैप में कुंजी और मानों के रूप में स्टोर करें। ए में मानों पर Iterate और बी (या शून्य) में अपनी स्थिति पाने के लिए उन्हें बी के हैश मैप में देखो। यदि यह स्थिति से पहले सबसे बड़ी स्थिति मान है जिसे आपने पहले देखा है, तो आप जानते हैं कि बी में कुछ ए (एन) समय में ए रन्स से भिन्न क्रम में है।

रफ, पूरी तरह से अपरीक्षित कोड:

boolean valuesInSameOrder(int[] A, int[] B) 
{ 
    Map<Integer, Integer> bMap = new HashMap<Integer, Integer>(); 
    for (int i = 0; i < B.length; i++) 
    { 
    bMap.put(B[i], i); 
    } 

    int maxPosInB = 0; 
    for (int i = 0; i < A.length; i++) 
    { 
    if(bMap.containsKey(A[i])) 
    { 
     int currPosInB = bMap.get(A[i]); 
     if (currPosInB < maxPosInB) 
     { 
     // B has something in a different order than A 
     return false; 
     } 
     else 
     { 
     maxPosInB = currPosInB; 
     } 
    } 
    } 

    // All of B's values are in the same order as A 
    return true; 
}