배열 요소의 다중 발생을 첫 번째 발생 순서로 그룹화

난이도 쉽게
자주 묻는 질문 수행자 어도비 벽돌 아마존 배달 포카이트
배열 해시조회수 32

분류되지 않은 질문을 받았습니다. 정렬 숫자가 여러 번 발생합니다. 작업은 배열 요소의 모든 다중 발생을 첫 번째 발생 순서로 그룹화하는 것입니다. 한편, 순서는 오는 번호와 동일해야합니다.

예

입력:

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

출력:

[2 2 3 3 3 4 4 1 XNUMX]

입력:

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

출력:

[5 5 5 4 4 1 1 6 XNUMX]

암호알고리즘

  1. 선언 해시맵.
  2. 배열을 탐색하고 모든 요소와 빈도를 HashMap에 넣습니다.
  3. 배열을 순회하면서 각 요소의 빈도를 가져옵니다.
    1. 해당 빈도 시간까지 해당 키를 인쇄하십시오.
    2. arr [i] (키)를 제거합니다.

배열 요소의 그룹 다중 발생에 대한 설명

우리는 그것을 위해 해싱을 사용할 것입니다. 해싱은 요소를 키-값 쌍으로 저장하는 기능을 제공합니다. 이 질문에서는 키를 배열 요소로 사용하고 값을 각 요소의 빈도로 사용할 것입니다. 해시 테이블에 없으면 요소를 삽입하기 만하면됩니다. 그렇지 않으면 요소의 개수 (키-값)를 늘립니다.

먼저 "myMap"이라는 HashMap을 선언합니다. 그런 다음 전체 배열을 탐색하고 주파수 각 요소의.

한 가지 예를 고려하고 이해합시다.

예

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이 두 번 인쇄되고 myMap에서 해당 키를 제거하므로 배열에서 2를 읽을 때마다 HashMap에 표시되지 않고 인쇄되지 않습니다.

이제 5가 배열로 나오지만 HashMap에는 존재하지 않으며 HashMap에있는 요소가 발견 될 때까지 아무것도하지 않습니다.

Arr [i] = 6 주파수 = 1

6이 인쇄되고 한 번이면 myMap에서 키가 제거되므로 배열에서 1를 읽을 때마다 hashmap에 존재하지 않고 인쇄하지 않습니다.

이제 출력은 5 5 5 4 4 1 1입니다.

실시

첫 번째 발생 순서로 배열 요소의 그룹 다중 발생을위한 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

자바 프로그램

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) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

참고

Translate »