按第一次出现顺序对数组元素进行分组多次出现


难度级别 易得奖学金
经常问 ol石 土砖 亚马逊 德里韦里 风筝
排列 哈希

给您一个问题,其中您给出了一个未分类的问题 排列 多次出现数字。 任务是将所有多次出现的数组元素按首次出现进行排序。 同时,顺序应与号码的顺序相同。

使用案列

输入:

[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. 声明 哈希图.
  2. 遍历数组并将所有元素及其频率放入HashMap中。
  3. 同时遍历数组并获取每个元素的频率。
    1. 最多打印该键一次。
    2. 删除该arr [i](键)。

数组元素分组多次出现的说明

我们将使用散列。 散列提供了将元素存储为键值对的功能。 在这个问题中,我们将使用键作为数组元素,并使用值作为每个元素的频率。 如果哈希表中不存在该元素,我们只需将其插入即可。 否则增加元素的数量(键值)。

首先,我们将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时,它就不会出现在哈希图中并且不会打印。

Arr [i] = 4频率= 2

4将被打印两次,该键将在myMap中删除,因此,每当我们在数组中读取2时,它就不会出现在HashMap中并且不会打印。

Arr [i] = 1频率= 2

1将被打印两次,然后我们将在myMap中删除该键,因此,只要我们在数组中读取2,它就不会出现在HashMap中并且不会打印。

现在有5个数组,但是它不会出现在HashMap中,并且同样会发生,并且不会执行任何操作,直到找到HashMap中存在的元素为止。

Arr [i] = 6频率= 1

6将被打印1次,该键将在myMap中删除,因此,每当我们在数组中读取4时,它就不会出现在哈希图中并且不会打印。

现在我们的输出为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” 是数组中元素的数量。

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。

参考