Массивын элементүүдийн бүлгийн олон давтамжийг эхний тохиолдлоор захиалсан болно  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Accolite Adobe Амазоны Дели Фуркайт
Array Хаш

Танд эрэмбэлэгдээгүй асуултыг өгсөн болно массив олон тооны давтамжтай. Даалгавар бол массивын элементүүдийн олон тохиолдлыг бүхэлд нь эхний илрэлээр захиалах явдал юм. Үүний зэрэгцээ, дугаар ирсэнтэй адил захиалга байх ёстой.

Жишээ нь  

Орц:

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

Үр дүн:

[2 2 3 3 3 4 4]

Орц:

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

Үр дүн:

[5 5 5 4 4 1 1]

Алгоритм  

  1. Тунхагла HashMap.
  2. Массивыг дайрч, бүх элементүүд болон давтамжийг HashMap-д оруулна уу.
  3. Массивыг дайран өнгөрөхдөө элемент бүрийн давтамжийг авна.
    1. Энэ түлхүүрийг тэр давтамж хүртэл хэвлэ.
    2. Тэр arr [i] (түлхүүр) -ийг хас.

Массивын элементүүдийн бүлгийн олон тохиолдлын талаархи тайлбар  

Үүний тулд бид Hashing-ийг ашиглах болно. Хэшлэх нь элементүүдийг түлхүүр утгын хос болгон хадгалах боломжийг олгодог. Энэ асуултанд бид түлхүүрийг массивын элемент болгон, утгыг элемент бүрийн давтамж болгон ашиглах болно. Хэш хүснэгтэд байхгүй бол бид элементийг оруулна. өөр бол элементийн тоог (түлхүүр утга) нэмэгдүүлэх.

Эхлээд бид 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

Массивын элементүүдийн бүлгийн олон тохиолдлын нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм.

мөн үзнэ үү
Хосолсон Leetcode шийдэл

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм.

лавлагаа