ຄວາມແຕກຕ່າງລະຫວ່າງຄວາມຖີ່ສູງສຸດແລະ ໜ້ອຍ ທີ່ສຸດໃນອາເລ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Citadel Fab ສີ່ພັນ ຟລີໂຄ້ດ Tesla
Array Hash ຮຽງລໍາດັບ

ບັນຫາ "ຄວາມແຕກຕ່າງລະຫວ່າງຄວາມຖີ່ສູງທີ່ສຸດແລະ ໜ້ອຍ ທີ່ສຸດໃນຂບວນການ" ລະບຸວ່າທ່ານມີ integer array. ຄຳ ຖະແຫຼງທີ່ມີບັນຫາຂໍໃຫ້ຄົ້ນພົບຄວາມແຕກຕ່າງລະຫວ່າງຄວາມຖີ່ສູງສຸດແລະຄວາມຖີ່ຕ່ ຳ ສຸດຂອງສອງຕົວເລກທີ່ແຕກຕ່າງກັນໃນຂບວນ ໜຶ່ງ.

ຍົກຕົວຢ່າງ

ຄວາມແຕກຕ່າງລະຫວ່າງຄວາມຖີ່ສູງສຸດແລະ ໜ້ອຍ ທີ່ສຸດໃນອາເລ

arr[] = {1, 2, 3, 1, 5, 2, 3, 1 }
2

ຄໍາອະທິບາຍ

ຄວາມຖີ່ຂອງການ 1 → 3 (ຄວາມຖີ່ສູງສຸດ)

ຄວາມຖີ່ຂອງ 5 → 1 (ຄວາມຖີ່ຕ່ ຳ ສຸດ)

arr[] = {5, 4, 5, 5, 5, 3, 4 }
3

ຄໍາອະທິບາຍ

ຄວາມຖີ່ຂອງການ 5 → 4 (ຄວາມຖີ່ສູງສຸດ)

ຄວາມຖີ່ຂອງ 3 → 1 (ຄວາມຖີ່ຕ່ ຳ ສຸດ)

ລະບົບວິເຄາະ

  1. ປະກາດກ ແຜນທີ່.
  2. ເກັບຮັກສາແລະນັບຄວາມຖີ່ຂອງອົງປະກອບຂບວນ.
  3. ທີ່ກໍານົດໄວ້ maxfreq ເຖິງ 0 ແລະ minfreq to n.
  4. ຂ້າມແຜນທີ່:
    1. ຊອກຫາມູນຄ່າສູງສຸດລະຫວ່າງ maxfreq ແລະຄວາມຖີ່ໃນແຜນທີ່ແລະເກັບມັນໄວ້ເປັນ maxfreq.
    2. ຊອກຫາມູນຄ່າ ຕຳ ່ສຸດລະຫວ່າງ minfreq ແລະຄວາມຖີ່ໃນແຜນທີ່ແລະເກັບມັນໄວ້ທີ່ minfreq.
  5. ກັບຄືນ (maxfreq-minfreq).

ຄໍາອະທິບາຍ

ພວກເຮົາມີແຖວເຕັມຂອງຕົວເລກ. ວຽກງານຂອງພວກເຮົາແມ່ນເພື່ອຊອກຫາຄວາມແຕກຕ່າງສູງສຸດລະຫວ່າງການເກີດຂື້ນທີ່ສູງທີ່ສຸດແລະການປະກົດຕົວທີ່ຕໍ່າທີ່ສຸດຂອງສອງຕົວເລກທີ່ແຕກຕ່າງກັນທີ່ມີຢູ່ໃນອາເລ. ພວກເຮົາ ກຳ ລັງຈະໃຊ້ ເຮື້ອຮັງ. Hashing ໃຫ້ວິທີການທີ່ມີປະສິດຕິຜົນໃນການແກ້ໄຂ ຄຳ ຖາມນີ້. ພວກເຮົາ ກຳ ລັງຈະປະກາດແຜນທີ່ແລະນັບຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບຂອງອາເລແລະພ້ອມກັນເກັບຄວາມຖີ່ພ້ອມກັບອົງປະກອບຕ່າງໆເຂົ້າໃນແຜນທີ່.

ຫຼັງຈາກນັ້ນພວກເຮົາຈະຕັ້ງຄ່າຂອງ maxfreq ເຖິງ 0 ແລະ minfreq ເຖິງ n, ຕົວຢ່າງ, ຄວາມຍາວຂອງອາເລເພາະວ່າບໍ່ມີອົງປະກອບໃດທີ່ມີຄວາມຖີ່ສູງກ່ວາຂະ ໜາດ ຂອງອາເລທີ່ໃຫ້. ພວກເຮົາຈະຂ້າມຜ່ານແຜນທີ່ແລະຈັບເອົາທຸກໆສ່ວນປະກອບ ໜຶ່ງ ເທື່ອແລະກວດເບິ່ງວ່າມັນມີຄວາມຖີ່ສູງສຸດຫລືຕໍ່າສຸດ. ແຍກຄວາມຖີ່ສູງສຸດໃຫ້ກັບຕົວປ່ຽນທີ່ແຕກຕ່າງກັນແລະຄວາມຖີ່ຕ່ ຳ ສຸດເປັນຕົວປ່ຽນທີ່ແຕກຕ່າງກັນ. ພວກເຮົາຕ້ອງກັບຄືນຄວາມແຕກຕ່າງລະຫວ່າງຄວາມຖີ່ສູງສຸດແລະຄວາມຖີ່ຕ່ ຳ ທີ່ສຸດ, ສະນັ້ນພວກເຮົາຈະກັບຄືນມາ (maxfreq-minfreq).

ຂໍໃຫ້ເຮົາຍົກຕົວຢ່າງ:

ຍົກຕົວຢ່າງ

arr [] = {1, 2, 3, 1, 5, 2, 3, 1}

ເມື່ອພວກເຮົາຂ້າມແຖວ, ພວກເຮົາຈະເອົາສ່ວນປະກອບແລະສິ່ງທີ່ບໍ່ເກີດຂື້ນຂອງພວກມັນເຂົ້າໄປໃນແຜນທີ່, ຫລັງຈາກຂ້າມຜ່ານພວກເຮົາຈະມີແຜນທີ່ດັ່ງນີ້:

ແຜນທີ່: {1: 3, 2: 2, 3: 2, 5: 1}

ດຽວນີ້, ພວກເຮົາມີການປະກົດຕົວຂອງແຕ່ລະອົງປະກອບໃນແຜນທີ່, ພວກເຮົາ ກຳ ລັງຈະຂ້າມແຜນທີ່, ແລະເກັບເອົາແຕ່ລະອົງປະກອບຈາກແຜນທີ່ແລະກວດເບິ່ງຄວາມຖີ່ຂອງມັນ, ເຊິ່ງແມ່ນຄວາມຖີ່ຫຼືຄວາມຖີ່ຂອງປະຈຸບັນທີ່ສູງກວ່າແລະມັນແມ່ນຄວາມຖີ່ປັດຈຸບັນຫລື minfreq ແລະເກັບມັນໄວ້ທີ່ maxfreq ແລະ minfreq ຕາມ ລຳ ດັບ.

  • 1: 3 →

3 ແມ່ນໃຫຍ່ກວ່າ maxfreq, ສະນັ້ນ maxfreq = 3

3 ມີຂະ ໜາດ ນ້ອຍກວ່າ minfreq, ສະນັ້ນ minfreq = 3

  • 2: 2 →

maxfreq ໃຫຍ່ກວ່າ 2, ສະນັ້ນ maxfreq = 3

2 ມີຂະ ໜາດ ນ້ອຍກວ່າ minfreq, ສະນັ້ນ minfreq = 2

  • 3: 2 →

maxfreq ໃຫຍ່ກວ່າ 2, ສະນັ້ນ maxfreq = 3

ບໍ່ມີຫຍັງປ່ຽນແປງໃນ minfreq, minfreq = 2

  • 5: 1 →

maxfreq ໃຫຍ່ກວ່າ 1, ສະນັ້ນ maxfreq = 3

1 ມີຂະ ໜາດ ນ້ອຍກວ່າ minfreq, ສະນັ້ນ minfreq = 1

ແລະພວກເຮົາຈະກັບຄືນຄວາມແຕກຕ່າງລະຫວ່າງ maxfreq-minfreq 3 (1-2) = XNUMX.

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຊອກຫາຄວາມແຕກຕ່າງລະຫວ່າງຄວາມຖີ່ສູງສຸດແລະ ໜ້ອຍ ທີ່ສຸດໃນອາເລ

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumDiff(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int maxfreq = 0, minfreq = n;
    for (auto x : freq)
    {
        maxfreq = max(maxfreq, x.second);
        minfreq = min(minfreq, x.second);
    }
    return (maxfreq - minfreq);
}
int main()
{
    int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumDiff(arr, n) << "\n";
    return 0;
}
2

ລະຫັດ Java ເພື່ອຊອກຫາຄວາມແຕກຕ່າງລະຫວ່າງຄວາມຖີ່ສູງສຸດແລະ ໜ້ອຍ ທີ່ສຸດໃນອາເລ

import java.util.HashMap;
import java.util.Map;

class diffBWHighFLeastF
{
    public static int getMaximumDiff(int arr[], int n)
    {
        HashMap<Integer,Integer> freq = new HashMap<>();
        for (int i = 0 ; i < n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i], freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i], 1);
            }
        }
        int maxfreq = 0, minfreq = n;
        for (Map.Entry<Integer,Integer> x : freq.entrySet())
        {
            maxfreq = Math.max(maxfreq, x.getValue());
            minfreq = Math.min(minfreq, x.getValue());
        }
        return (maxfreq - minfreq);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
        int n = arr.length;
        System.out.println(getMaximumDiff(arr, n));
    }
}
2

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

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ໃນທີ່ນີ້ພວກເຮົາໄດ້ຄົ້ນຫາແບບງ່າຍໆກ່ຽວກັບສ່ວນປະກອບຂອງຂບວນການຕິດຕາມຄວາມຖີ່ຂອງພວກມັນ. ທັງ ໝົດ ນີ້ຄ່າໃຊ້ຈ່າຍເວລາ O (N) ເທົ່ານັ້ນ.

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເກືອບທັງ ໝົດ, ພວກເຮົາສາມາດເກັບຮັກສາອົງປະກອບ n ຖ້າມັນທັງ ໝົດ ແຕກຕ່າງກັນ. ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນເປັນເສັ້ນ.