Rayանգվածային տարրերի խմբային բազմակի առաջացում ՝ պատվիրված ըստ առաջին դեպքի


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ակոլիտ Adobe Amazon Առաքում Ֆուրկիտներ
Դասավորություն Խանգարել

Ձեզ տրվում է մի հարց, որում դուք տվել եք չհավաքված դասավորություն թվերի բազմակի երեւույթներով: Խնդիրն այն է, որ խմբավորվի զանգվածի տարրերի բոլոր բազմակի դեպքերը, որոնք պատվիրված են առաջին դեպքի համաձայն: Մինչդեռ կարգը պետք է լինի նույնը, ինչ համարը գալիս է:

Օրինակ

Մուտք:

[2, 3,4,3,1,3,2,4]

Արդյունք:

[2 2 3 3 3 4 4 1]

Մուտք:

[5,4,1,5,4,1,5,6]

Արդյունք:

[5 5 5 4 4 1 1 6]

Ալգորիթմ

  1. Հայտարարել HashMap.
  2. Անցեք զանգվածը և դրեք բոլոր տարրերն ու դրա հաճախականությունը HashMap- ի մեջ:
  3. Traանգվածը անցնելիս և ստանալ յուրաքանչյուր տարրի հաճախականությունը:
    1. Տպեք այդ ստեղնը մինչև այդ հաճախականության ժամանակները:
    2. Հեռացնել այդ arr [i] (բանալին):

Rayանգվածի տարրերի խմբի բազմակի առաջացման բացատրություն

Մենք պատրաստվում ենք օգտագործել Հեշինգը դրա համար: Հաշինգը տալիս է տարրերը որպես հիմնական-արժեքային զույգ պահելու հատկություն: Այս հարցում մենք կօգտագործենք ստեղն որպես զանգվածի տարր և արժեք `որպես յուրաքանչյուր տարրի հաճախականություն: Մենք պարզապես տեղադրում ենք տարրը, եթե այն չկա հեշ աղյուսակում: այլապես մեծացնել տարրի հաշվարկը (բանալի-արժեք):

Նախ, մենք կհայտարարենք, որ HashMap- ն ասում է «myMap»: Դրանից հետո մենք անցնում ենք ամբողջ զանգվածը և հաշվում և պահպանում ենք այն հաճախություն յուրաքանչյուր տարրի:

Եկեք քննարկենք մի օրինակ և հասկանանք այն:

Օրինակ

arr = [5, 4, 1, 5, 4, 1, 5, 6]

i = 0, arr [i] = 5

myMap = {5: 1}

i = 1, arr [i] = 4

myMap = {4: 1,5: 1}

i = 2, arr [i] = 1

myMap = {1: 1,4: 1,5: 1}

i = 3, arr [i] = 5

myMap = {1: 1,4: 1,5: 2}

i = 4, arr [i] = 4

myMap = {1: 1,4: 2,5: 2}

i = 5, arr [i] = 1

myMap = {1: 2,4: 2,5: 2}

i = 6, arr [i] = 5

myMap = {1: 2,4: 2,5: 3}

i = 6, arr [i] = 6

myMap={1:2,4:2,5:3,6:1}

Այժմ դրա մեջ կունենանք myMap և արժեքներ:

Հաճախականությունը կստանանք զանգվածը կրկին զանգվածում տեղաշարժելուց հետո `զանգվածում պատվիրված տարրով: Յուրաքանչյուր զանգվածի տարրը վերցնելով իր հաճախականությամբ և կատարեք մի օղակ մինչև այդ հաճախականության ժամանակը, և զանգվածի բոլոր տարրերը տպելուց հետո, մինչև հաճախականության անգամները հեռացնեն այդ զանգվածի ստեղնը, որպեսզի այն հետագայում անցնի:

Arr [i] = 5 հաճախականություն = 3

5-ը կտպագրվի, 3 անգամ, այնուհետև մենք այդ բանալին կհեռացնենք myMap- ում, այնպես որ, երբ զանգվածում 5-ը կարդանք, այն չի լինի hashmap- ում և չի տպվում:

Arr [i] = 4 հաճախականություն = 2

4-ը կտպագրվի, 2 անգամ, բանալին կհեռացվի myMap- ում, այնպես որ, երբ մենք զանգվածում 4-ը կարդանք, այն չի լինի HashMap- ում և չի տպվում:

Arr [i] = 1 հաճախականություն = 2

1-ը կտպագրվի, 2 անգամ, այնուհետև մենք կհեռացնենք այդ բանալին myMap- ում, այնպես որ, երբ մենք զանգվածում կարդանք 5-ը, և այն չի լինի HashMap- ում և չի տպվում:

Այժմ 5-ը գալիս է զանգվածում, բայց այն չի լինի HashMap- ում, և նույնը պատահում է և ոչինչ չի ձեռնարկում, քանի դեռ չի հայտնաբերվել այն տարրը, որը առկա է HashMap- ում:

Arr [i] = 6 հաճախականություն = 1

6-ը կտպագրվի, 1 անգամ, բանալին կհեռացվի myMap- ում, այնպես որ, երբ զանգվածում 4-ը կարդանք, այն չի լինի hashmap- ում և չի տպվում:

Արդյունքն այժմ կունենանք 5 5 5 4 4 1 1 6:

Իրականացման

C ++ ծրագիր զանգվածի տարրերի բազմակի առաջացման համար

#include<iostream>
#include<unordered_map>

using namespace std;
void arrangeInOrder(int arr[], int n)
{
    unordered_map<int, int> myMap;

    for (int i=0; i<n; i++)
    {
        myMap[arr[i]]++;
    }
    for (int i=0; i<n; i++)
    {
        int count = myMap[arr[i]];
        for (int j=0; j<count; j++)
            cout<<arr[i]<< " ";

        myMap.erase(arr[i]);
    }
}
int main()
{
    int arr[] = {10, 5, 3, 10, 10, 4, 1, 3};
    int n=sizeof(arr)/sizeof(arr[0]);
    arrangeInOrder(arr,n);
    return 0;
}
10 10 10 5 3 3 4 1

Java ծրագիր

import java.util.HashMap;

class multipleOccurences
{
    public static void arrangeInOrder(int arr[])
    {
        HashMap<Integer, Integer> myMap= new HashMap<Integer, Integer>();

        for (int i=0; i<arr.length; i++)
        {
            Integer current = myMap.get(arr[i]);
            if (current == null)
                current = 0;

            myMap.put(arr[i], current + 1);
        }
        for (int i=0; i<arr.length; i++)
        {
            Integer count = myMap.get(arr[i]);
            if (count != null)
            {
                for (int j=0; j<count; j++)
                {
                    System.out.print(arr[i] + " ");
                }
                myMap.remove(arr[i]);
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 5, 3, 10, 10, 4, 1, 3};
        arrangeInOrder(arr);
    }
}
10 10 10 5 3 3 4 1

Բարդության վերլուծություն զանգվածի տարրերի խմբային բազմակի հայտնաբերման համար

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

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

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

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Մանրամասն