Массивад давхардсан бүхэл тоонууд байгаа эсэхийг шалгана уу  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accenture Амазоны Directi Facebook-ийн Intuit
Array Хаш String

Танд массив давхардсан элемент агуулж болох бүхэл тоо. Асуудлын шийдэл нь энэ нь зэргэлдээ бүхэл тоонуудын олонлог мөн эсэхийг олж мэдэхийг хүсч байгаа бол "Тийм" гэж хэвлэ, хэрэв үгүй ​​бол "Үгүй" гэж хэвлэ.

Жишээ нь  

Дээж оруулах:

[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.

Тайлбар  

Өгөгдсөн массив нь олонлогтой эсэхийг тодорхойлох асуултыг бидэнд өгсөн болно зэргэлдээ бүхэл тоо. Хэрэв энэ нь хэвлэгдсэн бол Тийм бол өөрөөр хэвлэнэ үү. Үгүй. Бид ашиглах болно багц Энэ нь бүх давхардсан элементүүдийг устгаж, бидний ажлыг хөнгөвчлөх гэж байгаа юм. Set нь зарим элемент нь давхардсан олон элементтэй бол ирээдүйг бий болгоно. Дараа нь бүх давхардсан хуулбарыг хасах бөгөөд зөвхөн ялгаатай элементүүдийг агуулах болно.

мөн үзнэ үү
Өгөгдсөн хоёр багц задарсан эсэхийг хэрхэн шалгах вэ?

Бид массивыг дайран өнгөрөх замаар бүх элементүүдийг оруулах болно нь чансаанд одоо энэ нь тодорхой элементүүдтэй байх болно. Тооны утгыг 1 болгож, дараа дараагийн үйлдлүүдэд үүнийг нэмэгдүүлэх болно. Энэ нь массивт зэргэлдээ бүхэл тоо байхгүй тохиолдолд Set-ээс өөр хэмжээтэй байх тул бүхэл тоонуудын зэргэлдээ олонлогийн хэмжээг шалгах болно. Arr [0] -1 нь currentElement-ийн утга байх болно. Энэ нь багцыг ажиглаж байх болно бүхэл тоо.

Циклийг нээгээд Set нь currentElement-ийг агуулах хүртэл үргэлжилнэ, учир нь бид давталтаар тооллын утгыг 1 (count = count + 1) -р өсгөж, currentElement-ийн утгыг 1 (currentElement = currentElement) -ээр бууруулна. - 1). CurrentElement-ийн утгыг arr [0] +1 гэж тохируулаад өөр нэг давталтыг нээгээд энэ нь Set дотор currentElement-ийг агуулах хүртэл үргэлжилсээр байх болно, гэхдээ энэ удаа бид 1 утгыг XNUMX count ++ ба currentElement ++ -р нэмэгдүүлэх болно. Эцэст нь тооллын утга нь Set-ийн хэмжээтэй тэнцүү эсэхийг шалгаж, хэрэв энэ нь үнэн болох нь тогтоогдвол return true return return нь худлаа болно.

Нэг жишээг авч үзье.

Жишээ нь

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

Массивыг дайрсны дараа бид Set-д дараах утгуудтай болно.

Давхардсан элементүүдийг устгах тул тохируулга: {2,3,4,5,6}

Count = 1, currentElement = arr [0] -1 = 4;

  • Set нь currentElement (4) утгатай бол үнэн,

Count = count + 1 => count = 2, currentElement– => currentElement = 3

  • Set нь currentElement (3) утгатай бол үнэн,

Count = count + 1 => count = 3, currentElement– => currentElement = 2

  • Set нь currentElement (2) утгатай бол үнэн,
мөн үзнэ үү
Элементүүд хүрээ хязгаарлагдаагүй тохиолдолд өгөгдсөн массиваас хуулбарыг ол

Count = count + 1 => count = 4, currentElement– => currentElement = 1

  • Set нь currentElement (1) утгатай бол худал тул давталтаас гарах болно.

CurrentElement [0] = arr [0] +1 => currentElement = 6-г тохируулна уу

  • Set нь currentElement (6) утгатай бол үнэн,

Count = count + 1 => count = 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" массив дахь элементүүдийн тоо юм.

мөн үзнэ үү
N бүхэл тоон массив дахь бүх хосуудын нийлбэр f (a [i], a [j])

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм.