रंग क्रमबद्ध करें  


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना ईबे Expedia Facebook गोल्डमैन सैक्स Nvidia ओरेकल
ऐरे छंटाई दो सूचक दो संकेत

रंगों को क्रमबद्ध करें एक समस्या है जिसमें हमें एक देना होगा सरणी एन ऑब्जेक्ट्स युक्त। प्रत्येक बॉक्स को एक ही रंग से रंगा गया है, जो लाल, नीला और सफेद हो सकता है। हमारे पास एन ऑब्जेक्ट हैं जो पहले से ही चित्रित हैं। हमें एरे को सॉर्ट करना होगा ताकि एक ही रंग की वस्तुएं लगातार आएं। यहाँ लाल रंग को 0 से चिह्नित किया गया है, सफेद रंग को 1 से चिह्नित किया गया है, और नीले रंग को क्रमशः 2 से चिह्नित किया गया है। आइए नीचे दी गई छवि में वर्णित एक उदाहरण देखें। छवि में, हम स्पष्ट रूप से देखते हैं कि सभी समान रंग की वस्तुएं एक दूसरे से सटे हैं। दो लाल वस्तुओं, तीन सफेद वस्तुओं और तीन नीले वस्तुओं को क्रमबद्ध क्रम में व्यवस्थित किया जाता है।

रंग क्रमबद्ध करेंपिन

नोट: हम एन ऑब्जेक्ट्स को सॉर्ट करने के लिए किसी भी पूर्वनिर्धारित लाइब्रेरी फ़ंक्शन का उपयोग नहीं कर सकते।

इनपुट प्रारूप

पहली-पंक्ति जिसमें एक पूर्णांक होता है जो सरणी में वस्तुओं की संख्या को दर्शाता है।

एन-पूर्णांक युक्त दूसरी-पंक्ति।

उत्पादन

सॉर्ट की गई सरणी को ऐसे प्रिंट करें कि दो समान-रंग की वस्तुएं हमेशा एक-दूसरे से सटे हों।

की कमी

  • 1 <= एन <= 100000
  • 0 <= एक [i] <= 2
6
0 1 0 2 1 2
0 0 1 1 2 2

व्याख्या

हम केवल 3 और 0,1 की संख्या की गणना करने के लिए 2 चर का उपयोग करते हैं। मतगणना के बाद हमने शून्य चर की गिनती का उपयोग करके शुरुआत करने के लिए सभी शून्य सेट किए।

और इसके बाद सभी को सेट करें और अंत में सभी को दो सेट करें।

सॉर्ट कलर्स के लिए एल्गोरिदम

Step:1 Set zero_count=0,one_count=0,two_count=0.
Step:2 For i in range 0 to N-1:
           If a[i] = 0 then:
               zero_count++.
           If a[i] = 1 then:
               one_count++.
           If a[i] = 2 then:
               two_count++.
Step:3 Set i=0.
Step:4 While(zero_count>0) then:
          a[i] = 0.
          zero_count--;
Step:5 While(one_count>0) then:
          a[i] = 1.
          one_count--;
Step:6 While(two_count>0) then:
          a[i] = 0.
          two_count--;
Step:7 Print the final array a.

सॉर्ट कलर्स के लिए कार्यान्वयन

/*C++ Implementation of Sort Colors.*/ 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{ 
    /*input values.*/ 
    int n; 
    cin>>n;
    int a[n];
    int zero_count=0,one_count=0,two_count=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        /*count all the same color objects.*/
        if(a[i]==0)
        {
            zero_count++;
        }
        else if(a[i]==1)
        {
            one_count++;
        }
        else
        {
            two_count++;
        }
    }
    int i=0;
    /*all objects with red color.*/
    while(zero_count>0)
    {
        a[i]=0;
        zero_count--;i++;
    }
    /*all object with white color.*/
    while(one_count>0)
    {
        a[i]=1;
        one_count--;i++;
    }
    /*all object with blue color.*/
    while(two_count>0)
    {
        a[i]=2;
        two_count--;i++;
    }
    /*print final result.*/
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0; 
}
6
1 2 1 0 2 0
0 0 1 1 2 2

समय जटिलता

पर) क्योंकि हम दिए गए सरणी के एन मान को प्रिंट करते हैं। यहां हम अंतिम परिणाम प्रिंट करने के लिए एक रैखिक लूप चलाते हैं।

यह भी देखें
ऊंचाई द्वारा कतार पुनर्निर्माण

अंतरिक्ष जटिलता

ओ (1) क्योंकि हम सिर्फ 3 चर का उपयोग एक ही रंग की वस्तुओं को गिनने के लिए करते हैं।

refrences