ການຮຽງລໍາດັບໂດຍໃຊ້ຫນ້າທີ່ hash trivial


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Cadence ອິນເດຍ Capgemini ປັດໃຈ MAQ UHG Optum
Array Hash ຮຽງລໍາດັບ

ບັນຫາ“ ການຈັດລຽງການ ນຳ ໃຊ້ ໜ້າ ທີ່ທີ່ບໍ່ ສຳ ຄັນ” ລະບຸວ່າທ່ານຖືກມອບໃຫ້ integer array. ອາເລສາມາດມີທັງຕົວເລກລົບແລະບວກ. ຄໍາຖະແຫຼງທີ່ມີບັນຫາຂໍໃຫ້ຈັດຮຽງການ ນຳ ໃຊ້ Hash Trivial Hash Function.

ຍົກຕົວຢ່າງ

ການຮຽງລໍາດັບໂດຍໃຊ້ຫນ້າທີ່ hash trivial

arr[] = {5,2,1,3,6}
{1, 2, 3, 5, 6}
arr[] = {-3, -1, 4, 3, -2, 1, 2, 0}
{-3, -2,-1, 0, 1, 2, 3, 4}

ຄໍາອະທິບາຍ

ທຸກໆອົງປະກອບຖືກຈັດຮຽງຕາມທັງຜົນໄດ້ຮັບ. ດັ່ງນັ້ນຜົນໄດ້ຮັບແມ່ນຖືກຕ້ອງ.

ລະບົບວິເຄາະ

  1. ຊອກຫາອົງປະກອບສູງສຸດແລະຕ່ ຳ ສຸດຂອງອາເລ (ອົງປະກອບຕ່ ຳ ສຸດແຕ່ມີຄ່າຢ່າງແທ້ຈິງ).
  2. ສ້າງຂບວນຂອງອົງປະກອບສູງສຸດຂອງຂະ ໜາດ ແລະອົງປະກອບຕ່ ຳ ສຸດ.
  3. ເພີ່ມການນັບຂອງຂບວນທັງສອງໂດຍ 1 ສຳ ລັບແຕ່ລະອົງປະກອບຕາມຄວາມ ເໝາະ ສົມຖ້າວ່າມັນໃຫຍ່ກວ່າ 0 ຫລືຕ່ ຳ ກ່ວາ 0 ແລະເກັບມ້ຽນໄວ້ໃນທັງສອງແຖວຕາມ ລຳ ດັບ.
  4. ພິມຂບວນທີ່ມີການນັບອົງປະກອບລົບ, ບໍ່ເທົ່າກັບເວລາທີ່ມັນເກີດຂື້ນ. ເຮັດສິ່ງດຽວກັນກັບອົງປະກອບໃນທາງບວກ.
  5. ພວກເຮົາຈະມີ ຈັດຮຽງ ຂບວນ.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ຮັບ array, ມັນສາມາດບັນຈຸເລກເຕັມບວກແລະລົບ. ວຽກງານຂອງພວກເຮົາແມ່ນຈັດຮຽງແຖວໂດຍໃຊ້ Trivial Hash function. ເພື່ອແກ້ໄຂບັນຫານີ້, ພວກເຮົາຈະ ນຳ ໃຊ້ hashing ແລະເລີ່ມຕົ້ນສອງອາຄານ. ຊອກຫາອົງປະກອບສູງສຸດແລະຕ່ ຳ ສຸດ (ອົງປະກອບຕ່ ຳ ສຸດທີ່ມີຄ່າຢ່າງແທ້ຈິງ). ໜຶ່ງ ແມ່ນ ສຳ ລັບອົງປະກອບລົບແລະອີກອັນ ໜຶ່ງ ແມ່ນ ສຳ ລັບອົງປະກອບໃນທາງບວກ. ຂະ ໜາດ ຂອງອາຄານທັງສອງຄວນຈະເທົ່າກັບສ່ວນປະກອບສູງສຸດຂອງວັດສະດຸປ້ອນແລະສ່ວນປະກອບລົບຂອງວັດສະດຸປ້ອນເຂົ້າແຕ່ມີຄ່າຢ່າງແທ້ຈິງ.

ພວກເຮົາຈະ ກຳ ລັງຂີດເສັ້ນແຖວທີ່ໃຫ້ໄວ້, ແລະກວດກາສະພາບການຖ້າວ່າຄ່າຂອງ array ທີ່ໃຫຍ່ກວ່າ 0, ພວກເຮົາຈະເພີ່ມຂື້ນຂື້ນ 1 ໃນ array ຂອງອົງປະກອບບວກແລະຖ້າມັນນ້ອຍກວ່າ 0, ມັນ ໝາຍ ຄວາມວ່າຕົວເລກແມ່ນລົບ, ພວກເຮົາ ຈະໄດ້ຮັບການເພີ່ມຂຶ້ນຂອງການປະກົດຕົວຂອງຕົນໂດຍ 1 ໃນອາເລອົງປະກອບທາງລົບ. ຫຼັງຈາກທີ່ຜ່ານການເລົ່າສູ່ກັນຟັງ, ພວກເຮົາມີການນັບ ຈຳ ນວນຂອງແຕ່ລະອົງປະກອບທີ່ໃຫ້ໃນທັງສອງຂບວນທີ່ພວກເຮົາສ້າງ.

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

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

ລະຫັດ C ++ ເພື່ອປະຕິບັດການຈັດລຽງໂດຍໃຊ້ ໜ້າ ທີ່ hash trivial

#include<iostream>
#include<unordered_map>
#include<algorithm>

using namespace std;

void sortUsingHash(int arr[], int n)
{
    int max = *std::max_element(arr, arr + n);
    int min = abs(*std::min_element(arr, arr + n));

    int positiveNum[max + 1] = { 0 };
    int negativeNum[min + 1] = { 0 };

    for (int i = 0; i < n; i++)
    {
        if (arr[i] >= 0)
            positiveNum[arr[i]] += 1;
        else
            negativeNum[abs(arr[i])] += 1;
    }
    for (int i = min; i > 0; i--)
    {
        if (negativeNum[i])
        {
            for (int j = 0; j < negativeNum[i]; j++)
            {
                cout << (-1) * i << " ";
            }
        }
    }
    for (int i = 0; i <= max; i++)
    {
        if (positiveNum[i])
        {
            for (int j = 0; j < positiveNum[i]; j++)
            {
                cout << i << " ";
            }
        }
    }
}
int main()
{
    int a[] = {7, 5, -4, -3, 2, 4, 1, -2, -1, 0, 6, 3 };

    int n = sizeof(a) / sizeof(a[0]);
    sortUsingHash(a, n);
    return 0;
}
-4 -3 -2 -1 0 1 2 3 4 5 6 7

ລະຫັດ Java ເພື່ອປະຕິບັດການຈັດຮຽງໂດຍໃຊ້ຟັງຊັນທີ່ບໍ່ ສຳ ຄັນ

import java.util.Arrays;
class HashingSorting
{
    public static void sortUsingHash(int arr[], int n)
    {
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Math.abs(Arrays.stream(arr).min().getAsInt());

        int positiveNum[] = new int[max + 1];
        int negativeNum[] = new int[min + 1];

        for (int i = 0; i < n; i++)
        {
            if (arr[i] >= 0)
                positiveNum[arr[i]] += 1;
            else
                negativeNum[Math.abs(arr[i])] += 1;
        }
        for (int i = min; i > 0; i--)
        {
            if (negativeNum[i] > 0)
            {
                for (int j = 0; j < negativeNum[i]; j++)
                {
                    System.out.print((-1)*i+" ");
                }
            }
        }
        for (int i = 0; i <= max; i++)
        {
            if (positiveNum[i] > 0)
            {
                for (int j = 0; j < positiveNum[i]; j++)
                {
                    System.out.print(i+" ");
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int a[] = { 7, 5, -4, -3, 2, 4, 1, -2, -1, 0, 6, 3 };
        int n = a.length;
        sortUsingHash(a, n);
    }
}
-4 -3 -2 -1 0 1 2 3 4 5 6 7

ການວິເຄາະຄວາມສັບສົນ

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

O (ສູງສຸດ + ນາທີ), ທີ່ນີ້ສູງສຸດທີ່ເຄຍແມ່ນອົງປະກອບສູງສຸດແລະຕໍາ່ສຸດທີ່ໃນການປ້ອນຂໍ້ມູນ. ດັ່ງນັ້ນຄວາມສັບສົນຂອງເວລາບໍ່ແມ່ນຂື້ນກັບຂະ ໜາດ ຂອງວັດສະດຸປ້ອນເຂົ້າແຕ່ມັນຂື້ນກັບອົງປະກອບຂອງມັນ.

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

O (ສູງສຸດ + ນາທີ), ທີ່ນີ້ສູງສຸດທີ່ເຄຍແມ່ນອົງປະກອບສູງສຸດແລະຕໍາ່ສຸດທີ່ໃນການປ້ອນຂໍ້ມູນ. ຄວາມສັບສົນຂອງພື້ນທີ່ກໍ່ຄືກັນກັບຄວາມສັບສົນຂອງເວລາ, ມັນຍັງບໍ່ຂຶ້ນກັບຂະ ໜາດ ຂອງວັດສະດຸປ້ອນເຂົ້າ. ມັນຂື້ນກັບຂະ ໜາດ ຂອງອົງປະກອບ.