按第一次出現的順序對數組元素進行分組多次出現  


難度級別 容易獎學金
經常問 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” 是數組中元素的數量。

也可以看看
組合總和Leetcode解決方案

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。

參考文獻