ການປະກົດຂື້ນຫຼາຍຄັ້ງໃນກຸ່ມຂອງອົງປະກອບ Array ຖືກສັ່ງໂດຍການປະກົດຕົວຄັ້ງ ທຳ ອິດ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Adobe Amazon ເດລີ ສີ່ພັນ
Array Hash

ທ່ານໄດ້ຮັບ ຄຳ ຖາມທີ່ທ່ານໃຫ້ ຄຳ ຖາມທີ່ບໍ່ຖືກຄັດເລືອກ array ມີການປະກົດຕົວຫຼາຍຕົວເລກ. ໜ້າ ວຽກແມ່ນຈັດກຸ່ມທຸກເຫດການທີ່ເກີດຂື້ນຫຼາຍຄັ້ງຂອງອົງປະກອບອາເລທີ່ສັ່ງໂດຍການເກີດຂື້ນຄັ້ງ ທຳ ອິດ ໃນຂະນະດຽວກັນ, ຄຳ ສັ່ງຄວນຄືກັບ ຈຳ ນວນທີ່ມາ.

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ:

[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. ໃນຂະນະທີ່ ກຳ ລັງຂ້າມແຖວແລະໄດ້ຮັບຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບ.
    1. ພິມລະຫັດນັ້ນໃສ່ເວລາຄວາມຖີ່ນັ້ນ.
    2. ເອົາທີ່ມາ [i] (ກະແຈ).

ຄໍາອະທິບາຍສໍາລັບກຸ່ມທີ່ເກີດຂື້ນຫຼາຍຄັ້ງຂອງອົງປະກອບ Array

ພວກເຮົາ ກຳ ລັງຈະໃຊ້ Hashing ສຳ ລັບມັນ. Hashing ໃຫ້ຄຸນລັກສະນະຂອງການເກັບຮັກສາອົງປະກອບດັ່ງກ່າວເປັນຄູ່ທີ່ມີຄ່າ. ໃນ ຄຳ ຖາມນີ້, ພວກເຮົາ ກຳ ລັງຈະໃຊ້ຄີເປັນອົງປະກອບອາເລແລະມູນຄ່າເປັນຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບ. ພວກເຮົາພຽງແຕ່ໃສ່ອົງປະກອບຖ້າມັນບໍ່ຢູ່ໃນຕາຕະລາງ hash. ອີກຢ່າງ ໜຶ່ງ ເພີ່ມການນັບ (key-value) ຂອງອົງປະກອບ.

ກ່ອນອື່ນ ໝົດ, ພວກເຮົາຈະປະກາດ ຄຳ ເວົ້າ HashMap ທີ່ເວົ້າວ່າ“ myMap”. ພວກເຮົາຫຼັງຈາກນັ້ນ traverse ອາເລທັງຫມົດແລະນັບແລະເກັບຮັກສາໄດ້ ຄວາມຖີ່ ຂອງແຕ່ລະອົງປະກອບ.

ໃຫ້ພວກເຮົາພິຈາລະນາຕົວຢ່າງແລະເຂົ້າໃຈມັນ.

ຍົກຕົວຢ່າງ

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

i = 0, ມາຮອດ [i] = 5

myMap = {5: 1}

i = 1, ມາຮອດ [i] = 4

myMap = {4: 1,5: 1}

i = 2, ມາຮອດ [i] = 1

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

i = 3, ມາຮອດ [i] = 5

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

i = 4, ມາຮອດ [i] = 4

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

i = 5, ມາຮອດ [i] = 1

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

i = 6, ມາຮອດ [i] = 5

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

i = 6, ມາຮອດ [i] = 6

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

ຕອນນີ້ພວກເຮົາຈະມີ myMap ແລະຄ່າຕ່າງໆໃນນັ້ນ.

ພວກເຮົາຈະໄດ້ຮັບຄວາມຖີ່ຫຼັງຈາກຜ່ານອາເລອີກເທື່ອ ໜຶ່ງ ດ້ວຍອົງປະກອບທີ່ຖືກສັ່ງໃນອາເລ. ເອົາແຕ່ລະອົງປະກອບ array ພ້ອມກັບຄວາມຖີ່ຂອງມັນແລະສ້າງ loop ຈົນເຖິງເວລາຄວາມຖີ່ນັ້ນແລະຫລັງຈາກທີ່ພິມ element ທັງ ໝົດ array ຈົນກ່ວາເວລາຄວາມຖີ່ຈະລົບຄີ array ດັ່ງນັ້ນມັນຈະບໍ່ພິມອີກຄັ້ງໃນ traversal ຕໍ່ໄປ

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 ++ ສຳ ລັບກຸ່ມຫຼາຍໆເຫດການທີ່ເກີດຂື້ນຂອງອົງປະກອບ Array ທີ່ຖືກສັ່ງໂດຍການເກີດຄັ້ງ ທຳ ອິດ

#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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບຫຼາຍໆກຸ່ມທີ່ເກີດຂື້ນຂອງອົງປະກອບ Array

ຄວາມສັບສົນເວລາ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

ກະສານອ້າງອີງ