ຊອກຫາອົງປະກອບທີ່ຂາດຫາຍໄປຂອງຊ່ວງໃດ ໜຶ່ງ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ເດລີ GreyOrange LinkedIn ນາກາໂຣ Opera Synopsys
Hash Larsen & Toubro ຮຽງລໍາດັບ

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

ຍົກຕົວຢ່າງ

ຊອກຫາອົງປະກອບທີ່ຂາດຫາຍໄປຂອງຊ່ວງໃດ ໜຶ່ງ

arr[] = [1, 3, 5, 7, 8, 9]

low=1 high = 10
2, 4, 6, 10

ຄໍາອະທິບາຍ

ເຫຼົ່ານີ້ແມ່ນຕົວເລກທີ່ຂາດຫາຍໄປໃນອາເລພາຍໃນຂອບເຂດທີ່ກ່າວໄວ້ຕ່ ຳ ແລະສູງເຊັ່ນ: 1 ແລະ 10.

arr[] = [2, 3, 7, 8]

low=1 high = 9
1, 4, 5, 6, 9

ຄໍາອະທິບາຍ

ເຫຼົ່ານີ້ແມ່ນຕົວເລກທີ່ຂາດຫາຍໄປໃນອາເລພາຍໃນຂອບເຂດທີ່ກ່າວໄວ້ຕ່ ຳ ແລະສູງເຊັ່ນ: 1 ແລະ 10.

ລະບົບວິເຄາະ

  1. ປະກາດກ ທີ່ກໍານົດໄວ້.
  2. ລອກເອົາອາເລແລະວາງອົງປະກອບທັງ ໝົດ ເຂົ້າໃນຊຸດ.
  3. ໃນຂະນະທີ່“ i” ເທົ່າກັບລະດັບຕໍ່າແລະ“ i” ແມ່ນ ໜ້ອຍ ກ່ວາທີ່ສູງ.
    • ຖ້າຊຸດ ໜຶ່ງ ບໍ່ມີ“ i”.
      • ພິມ 'i'.

ຄໍາອະທິບາຍ

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

ເພື່ອໃຫ້ໄດ້ຮັບ ຄຳ ສັ່ງດັ່ງກ່າວພວກເຮົາເກັບບັນດາອົງປະກອບຂອງຂບວນໄວ້ໃນຊຸດແລ້ວ. ພວກເຮົາ ຈຳ ເປັນຕ້ອງ ດຳ ເນີນ loop ທີ່ເລີ່ມຕົ້ນ 'i' ຕ່ ຳ. ພວກເຮົາດໍາເນີນການ loop ຈົນກ່ວາມູນຄ່າຂອງ 'i' ສູງ. ຫຼັງຈາກນັ້ນໃຫ້ກວດເບິ່ງວ່າຊຸດທີ່ບໍ່ມີຄ່າ 'i' ແລ້ວພິມ 'i'. ດັ່ງນັ້ນພວກເຮົາຈະໄດ້ຮັບສ່ວນປະກອບທັງ ໝົດ ທີ່ຂາດຈາກອາເລພາຍໃນຂອບເຂດໃດ ໜຶ່ງ. ຂໍໃຫ້ເຮົາພິຈາລະນາຕົວຢ່າງ.

arr [] = {2, 3, 7, 8} ຕ່ ຳ = 1, ສູງ = 9

ພວກເຮົາ ຈຳ ເປັນຕ້ອງຂ້າມອາເລແລະວາງທຸກສ່ວນຂອງອາເລເຂົ້າໃນຊຸດ. ຊຸດຂອງພວກເຮົາຈະກາຍເປັນ

ຊຸດ = [2,3,7,8]

ໃນ loop ເລີ່ມຕົ້ນ i ໃຫ້ຕ່ ຳ ແລະ loop ແລ່ນຈົນສູງ, ມັນ ໝາຍ ຄວາມວ່າ 'i' ເທົ່າກັບຕ່ ຳ = 1 ແລະສູງ = 9

i = 1, ຖ້າຊຸດບໍ່ມີ i, ພິມ 1

[ປີ 1]

i = 2, ຊຸດມີຄ່າ '2' ແລະບໍ່ເຮັດຫຍັງເລີຍ.

i = 3, ຊຸດມີຄ່າ '3' ແລະບໍ່ເຮັດຫຍັງເລີຍ.

i = 4, ຖ້າຊຸດບໍ່ມີ i, ພິມ 4

[1, 4]

i = 5, ຖ້າຊຸດບໍ່ມີ i, ພິມ 5

[1, 4, 5]

i = 6, ຖ້າຊຸດບໍ່ມີ i, ພິມ 6

[1, 4, 5, 6]

i = 7, ຊຸດມີຄ່າ '7' ແລະບໍ່ເຮັດຫຍັງເລີຍ.

i = 8, ຊຸດມີຄ່າ '8' ແລະບໍ່ເຮັດຫຍັງເລີຍ.

i = 9, ຖ້າຊຸດບໍ່ມີ i, ພິມ 1

[1, 4, 5, 6, 9]

ຜົນຜະລິດຂອງພວກເຮົາຈະກາຍເປັນ: [1, 4, 5, 6, 9]

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຊອກຫາອົງປະກອບທີ່ຂາດຫາຍໄປຂອງຊ່ວງໃດ ໜຶ່ງ

#include <unordered_set>
#include<iostream>

using namespace std;

void getMissingElements(int arr[], int n, int low, int high)
{
    unordered_set<int> myset;
    for (int i = 0; i < n; i++)
        myset.insert(arr[i]);

    for (int x = low; x <= high; x++)
        if (myset.find(x) == myset.end())
            cout << x << " ";
}
int main()
{
    int arr[] = { 2,3,7,8 };
    int low = 1, high = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    getMissingElements(arr, n, low, high);
    return 0;
}
1 4 5 6 9

ລະຫັດ Java ເພື່ອຊອກຫາອົງປະກອບທີ່ຂາດຫາຍໄປຂອງຊ່ວງໃດ ໜຶ່ງ

import java.util.HashSet;

class RangeMissingElements
{
    public static void getMissingElements(int arr[], int low, int high)
    {
        HashSet<Integer> myset = new HashSet<>();

        for (int i = 0; i < arr.length; i++)
        {
            myset.add(arr[i]);
        }

        for (int i = low; i <= high; i++)
        {
            if (!myset.contains(i))
            {
                System.out.print(i + " ");
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,7,8};
        int low = 1, high = 9;
        getMissingElements(arr, low, high);
    }
}
1 4 5 6 9

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

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

O (n + (ສູງຕ່ ຳ + 1)) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງສ່ວນປະກອບທີ່ມີຢູ່ໃນແຖວ, “ ສູງ” ແລະ “ ຕ່ ຳ” ແມ່ນວັດສະດຸປ້ອນໃຫ້.

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

ໂອ (n), ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ, ຖ້າວ່າທຸກໆອົງປະກອບແຕກຕ່າງ. ພວກເຮົາຈະຕ້ອງເກັບສ່ວນປະກອບທັງ ໝົດ ໄວ້. ດັ່ງນັ້ນການເຮັດໃຫ້ສູດການຄິດໄລ່ຕ້ອງໃຊ້ເວລາເປັນເສັ້ນ.