ກວດເບິ່ງວ່າ Array ມີສ່ວນປະກອບທີ່ຕິດພັນກັບສິ່ງທີ່ຊ້ ຳ ຊ້ອນອະນຸຍາດ  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Accenture Amazon Directi ເຟສບຸກ Intuit
Array Hash string

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

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນຕົວຢ່າງ:

[2, 3, 4, 1, 7, 9]

ຜົນໄດ້ຮັບຕົວຢ່າງ:

ແມ່ນ​ແລ້ວ

ຄໍາອະທິບາຍ:

ມັນມີຊຸດຂອງຕົວເລກເຊື່ອມຕໍ່ຕິດຕໍ່ກັນຂອງເລກ [2, 3, 4, 1]

ສູດການຄິດໄລ່ເພື່ອກວດກາເບິ່ງວ່າອາເລມີຕົວເລກທີ່ຕິດຢູ່ກັບຊໍ້າຊ້ອນທີ່ອະນຸຍາດ  

1. Declare a Set.
2. Add all the elements of an array into the Set.
3. Set count to 1 and currentElement to arr[0]-1.
4. Open a loop, while Set contains the currentElement.
  1. Do count++ and currentElement--.
5. Set currentElement to arr[0]+1.
6. Open a loop, while Set contains the currentElement.
  1. Do count++ and currentElement++.
7. Check if the count is equal to the size of a set, if condition satisfies, then return true.
8. Else return false.

ຄໍາອະທິບາຍ  

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

ເບິ່ງ
ວິທີການກວດສອບຖ້າສອງຊຸດທີ່ຖືກມອບໃຫ້ຖືກກຽດຊັງ?

ພວກເຮົາ ກຳ ລັງຈະໃສ່ອົງປະກອບທັງ ໝົດ ໂດຍຜ່ານການເຂົ້າແຖວ ທີ່ກໍານົດໄວ້ ແລະມັນຈະມີສ່ວນປະກອບທີ່ແຕກຕ່າງກັນໃນຕອນນີ້. ກໍານົດມູນຄ່າຂອງການນັບເປັນ 1 ແລະພວກເຮົາຈະສືບຕໍ່ເພີ່ມຂື້ນໃນການດໍາເນີນງານຕໍ່ມາ. ມັນຈະກວດເບິ່ງຂະ ໜາດ ຂອງຕົວເລກທີ່ຕິດຕໍ່ກັນຂອງຕົວເລກບວກເພາະວ່າມັນຈະມີຂະ ໜາດ ແຕກຕ່າງກັນກ່ວາທີ່ ກຳ ນົດໄວ້ຖ້າວ່າບໍ່ມີຕົວເລກທີ່ຕິດຕໍ່ກັນຢູ່ໃນອາເລ. ການມາຮອດ [0] -1 ຈະເປັນມູນຄ່າຂອງປະຈຸບັນ. ມັນຈະຮັກສາຕາໃນຊຸດຂອງ integers.

ເປີດ Loop ແລະມັນຈະສືບຕໍ່ໄປຈົນກວ່າ Set ມີ currentElement ຢູ່ໃນນັ້ນ, ເພາະວ່າໃນ loop ພວກເຮົາຈະເຮັດໃຫ້ຄ່າຂອງ count ນັບ 1 (count = count + 1) ແລະຫຼຸດຄ່າຂອງ currentElement ໂດຍ 1 (currentElement = currentElement) - 1). ກຳ ນົດຄ່າຂອງ currentElement ມາຮອດ [0] +1 ແລະເປີດ loop ອີກອັນ ໜຶ່ງ ແລະມັນຍັງຈະສືບຕໍ່ໄປຈົນກວ່າ ກຳ ນົດມີ currentElement ຢູ່ໃນນັ້ນ, ແຕ່ຄັ້ງນີ້ພວກເຮົາຈະເພີ່ມຄ່າທັງສອງໂດຍ 1 count ++ ແລະ currentElement ++. ໃນທີ່ສຸດ, ພວກເຮົາຈະກວດເບິ່ງວ່າມູນຄ່າຂອງການນັບແມ່ນເທົ່າກັບຂະ ໜາດ ຂອງທີ່ ກຳ ນົດໄວ້, ຖ້າພົບວ່າມີມູນຄວາມຈິງແລ້ວຈະສົ່ງຄືນອີກຂອງຈິງບໍ່ຖືກຕ້ອງ.

ຂໍໃຫ້ເຮົາພິຈາລະນາຕົວຢ່າງ:

ຍົກຕົວຢ່າງ

arr [] = {5, 2, 3, 6, 4, 4, 6, 6};

ຫຼັງຈາກຜ່ານແຖວ, ພວກເຮົາຈະມີຄຸນຄ່າຕໍ່ໄປນີ້ໃນ Set.

ກຳ ນົດ: {2,3,4,5,6}, ຍ້ອນວ່າມັນ ກຳ ຈັດອົງປະກອບທີ່ຊ້ ຳ ກັນອອກ

ນັບ = 1, currentElement = ມາຮອດ [0] -1 = 4;

  • ໃນຂະນະທີ່ Set ມີ currentElement (4) ເປັນຄວາມຈິງ,

ນັບ = ນັບ + 1 => ນັບ = 2, currentElement– => currentElement = 3

  • ໃນຂະນະທີ່ Set ມີ currentElement (3) ເປັນຄວາມຈິງ,

ນັບ = ນັບ + 1 => ນັບ = 3, currentElement– => currentElement = 2

  • ໃນຂະນະທີ່ Set ມີ currentElement (2) ເປັນຄວາມຈິງ,
ເບິ່ງ
ຊອກຫາສິ່ງທີ່ຊ້ ຳ ຊ້ອນກັນໃນແຖວທີ່ ກຳ ນົດໄວ້ເມື່ອອົງປະກອບຕ່າງໆບໍ່ ຈຳ ກັດຢູ່ໃນຂອບເຂດໃດ ໜຶ່ງ

ນັບ = ນັບ + 1 => ນັບ = 4, currentElement– => currentElement = 1

  • ໃນຂະນະທີ່ Set ມີ currentElement (1) ແມ່ນບໍ່ຖືກຕ້ອງ, ສະນັ້ນມັນອອກມາຈາກວົງຈອນ.

ຕັ້ງຄ່າ currentElement [0] = ມາຮອດ [0] +1 => currentElement = 6

  • ໃນຂະນະທີ່ Set ມີ currentElement (6) ເປັນຄວາມຈິງ,

ນັບ = ນັບ + 1 => ນັບ = 5, currentElement ++ => currentElement = 7

  • ໃນຂະນະທີ່ Set ມີ currentElement (7) ແມ່ນບໍ່ຖືກຕ້ອງດັ່ງນັ້ນມັນອອກມາຈາກວົງຈອນ

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

ການປະຕິບັດ  

ລະຫັດ C ++ ເພື່ອກວດເບິ່ງວ່າແຖວນັ້ນມີຕົວເລກທີ່ຕິດຢູ່ກັບຕົວເລກທີ່ຊ້ ຳ ຊ້ອນກັນ

#include<iostream>
#include<unordered_set>
using namespace std;
bool areElementsContiguous(int arr[], int n)
{
    unordered_set<int> Set;
    for (int i = 0; i < n; i++)
        Set.insert(arr[i]);

    int count = 1;
    int currentElement = arr[0] - 1;
    while (Set.find(currentElement) != Set.end())
    {
        count++;
        currentElement--;
    }
    currentElement = arr[0] + 1;
    while (Set.find(currentElement) != Set.end())
    {
        count++;
        currentElement++;
    }
    return (count == (int)(Set.size()));
}
int main()
{
    int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (areElementsContiguous(arr, n))
        cout << "Yes, it is set of contiguous integers.";
    else
        cout << "No, it is not a set of contiguous integers.";
    return 0;
}
Yes, it is set of contiguous integers.

ລະຫັດ Java ເພື່ອກວດສອບວ່າອາເລປະກອບມີເລກເຕັມທີ່ມີສ່ວນປະກອບທີ່ຊ້ ຳ ກັນ

import java.util.HashSet;
class contiguousArray
{
    public static Boolean checkContiguousElements(int arr[], int n)
    {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            set.add(arr[i]);
        }
        int count = 1;
        int currentElement = arr[0] - 1;
        while (set.contains(currentElement) == true)
        {
            count++;
            currentElement--;
        }
        currentElement = arr[0] + 1;
        while (set.contains(currentElement) == true)
        {
            count++;
            currentElement++;
        }
        return (count == (set.size()));
    }
    public static void main(String[] args)
    {
        int arr[] = { 10, 7, 8, 11, 9, 9, 10, 10 };
        int n = arr.length;
        if (checkContiguousElements(arr, n))
            System.out.println("Yes, it is set of contiguous integers.");
        else
            System.out.println("No, it is not a set of contiguous integers.");
    }
}
Yes, it is set of contiguous integers.

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

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

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

ເບິ່ງ
ຜົນບວກຂອງ f (a [i], a [j]) ເໜືອ ທຸກຄູ່ໃນແຖວຂອງຕົວເລກ n

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

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