Տեսակավորել 0-ները 1-ը և 2-ը զանգվածում  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon Զբոսանք MakeMyTrip- ը MAQ Microsoft Morgan Stanley Օլա Քաբս Paytm Qualcomm SAP լաբորատորիաներ Snapdeal Walmart Labs Yatra
Դասավորություն Տեսակ դասավորում

Խնդիրի հայտարարություն  

Հաշվի առնելով N տարրեր պարունակող զանգված, որտեղ տարրերը դասավորություն են 0,1 կամ 2. Տեսակավորել կամ առանձնացնել 0-ից 1-ը և 2-ը զանգվածում: Դասավորեք բոլոր զրոները առաջին կեսում, բոլորը երկրորդ կեսում և բոլոր երկվորյակները երրորդ կեսում:

Օրինակ  

Մուտքային

22

0 1 2 0 1 1 1 1 1 0 1 2 1 0 2 2 2 0 1 2

Արտադրողականություն

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2

Մոտեցում 1  

Ալգորիթմ

1. Պարզապես ստեղծեք 3 չափի count_array և նախանշեք զանգվածի բոլոր տարրերը զրո:
2. count_array զանգվածի տարրը պատկերում է i ցուցիչի դեպքերի քանակը:
3. Տարանցել տրված զանգվածը, և եթե մենք 0 աճ ենք ստանում count_array- ի 0-րդ ցուցանիշը և նմանապես անում ենք 1-ի և 2-ի համար `ավելացնելով 1-ին և 2-րդ ինդեքսի արժեքի count_array- ը:
4. Վերջապես տպիր 0-ի, 1-ի և 2-ի քանակը նույնքան անգամ, որքան count_array տարրի արժեքը:

Իրականացում զանգվածում 0-ների 1-ի և 2-ների տեսակավորման համար

C ++ ծրագիր

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
      cin>>arr[i];
    }
    int cnt[3]={0};//hashing approach
    for(int i=0;i<N;i++)
    cnt[arr[i]]++;//increase the count of that index 
    for(int i=0;i<3;i++)
    for(int j=0;j<cnt[i];j++)//print that index as many times its value is
      cout<<i<<" ";
  return 0;
}

Java ծրագիր

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int cnt[] = new int [3];//hashing approach
        cnt[0]=0;cnt[1]=0;cnt[2]=0;
        for(int i=0;i<n;i++)
        cnt[a[i]]++;//increase the count of that index 
        for(int i=0;i<3;i++)
        for(int j=0;j<cnt[i];j++)//print that index as many times its value is
            System.out.print(i+" ");
       }
}
22
0 1 2 0 1 1 1 1 1 0 1 2 1 0 2 2 2 0 1 2 0 1
0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2

Բարդության վերլուծություն

Timeամանակի բարդություն 

ՎՐԱ) որտեղ n - զանգվածի չափը: Այստեղ մենք անցնում ենք զանգվածը և հաշվում նույն տեսակի տարրերը:

Տես նաեւ,
Հերթի առաջին K տարրերի հակադարձում

Տիեզերական բարդություն

Ո (1) քանի որ մենք այստեղ անընդհատ տարածություն ենք օգտագործում:

Մոտեցում 2  

Ալգորիթմ

1. Պարզապես տեսակավորեք զանգվածը (օգտագործելով կամ Heap / Merge տեսակավորումը կամ օգտագործելով sort () STL գործառույթը):
2. Պարզապես տպեք տեսակավորված զանգվածը:

Իրականացում զանգվածում 0-ների 1-ի և 2-ների տեսակավորման համար

C ++ ծրագիր

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
      cin>>arr[i];
    }
    sort(arr,arr+N);//sort the array simply
    for(int i=0;i<N;i++)
    cout<<arr[i]<<" ";
    return 0;
}

Java ծրագիր

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a);
        for(int j=0;j<n;j++)
            System.out.print(a[j]+" ");
     }
}
10
0 1 2 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1 1 2

Բարդության վերլուծություն

Timeամանակի բարդություն

O (NlogN) քանի որ մենք օգտագործում ենք ներբանկային տեսակավորման գործառույթ, որն ունի ժամանակի բարդություն:

Տիեզերական բարդություն

Ո (1) քանի որ մենք այստեղ ոչ մի օժանդակ տարածք չենք օգտագործում:

Սայլակ