Rəngləri sırala

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon eBay Expedia Facebook Goldman Sachs Nvidia Kahin
Geyim çeşidləyici İki işarə İki işarəBaxılıb 26

Rəngləri çeşidləyin verməli olduğumuz bir problemdir array tərkibində N obyekt var. Hər qutu qırmızı, mavi və ağ ola biləcək bir rənglə boyanır. Artıq boyanmış N obyektimiz var. Dizini eyni rəngli obyektlərin davamlı gəlməsi üçün sıralamalıyıq. Burada Qırmızı rəng 0 ilə, Ağ rəng 1 ilə, Mavi rəng 2 ilə işarələnir. Aşağıdakı şəkildə təsvir olunan bir nümunəyə baxaq. Şəkildə eyni rəngli cisimlərin bir-birinə bitişik olduğunu açıq şəkildə görürük. İki qırmızı cisim, üç ağ cisim və üç mavi cisim sıralanmış qaydada düzülmüşdür.

Rəngləri sıralaPin

Qeyd: N obyektlərini sıralamaq üçün əvvəlcədən təyin edilmiş kitabxana funksiyasından istifadə edə bilmərik.

Giriş Formatı

Dizidəki obyektlərin sayını göstərən bir tam ədədi ehtiva edən birinci sətir.

N tam ədədi olan ikinci sətir.

Buraxılış

Sıralanmış massivi iki eyni rəngli cisim həmişə bir-birinə bitişik olacaq şəkildə çap edin.

Məhdudiyyətlər

  • 1 <= N <= 100000
  • 0 <= a [i] <= 2
6
0 1 0 2 1 2
0 0 1 1 2 2

Izahat

3 və 0,1 saylarını saymaq üçün sadəcə 2 dəyişəndən istifadə edirik. Sayı verdikdən sonra əvvəlcə sıfır dəyişən sayını istifadə edərək sıfırın başlanğıcını təyin etdik.

Və hamısını qurduqdan sonra, sonunda ikisini də qurdu.

Çeşidləmə rəngləri üçün alqoritm

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.

Çeşidləmə rəngləri üçün tətbiqetmə

/*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

Zamanın mürəkkəbliyi

O (N) çünki verilmiş massivin N dəyərlərini çap edirik. Burada son nəticəni çap etmək üçün bir xətti döngə işlədirik.

Kosmik Mürəkkəblik

O (1) çünki eyni rəngli obyektləri saymaq üçün sadəcə 3 dəyişəndən istifadə edirik.

Yenidənqurma

Translate »