შეამოწმეთ, შეიცავს თუ არა მასივი ნებადართულ დუბლიკატებთან მომიჯნავე მთელი რიცხვები


Რთული ტური საშუალო
ხშირად ეკითხებიან Accenture Amazon დირექტი Facebook Intuit
Array Hash სიმებიანი

თქვენ გეძლევათ მასივი მთელი რიცხვებისა, რომლებიც შეიძლება შეიცავდეს დუბლიკატ ელემენტებსაც. პრობლემის დებულება ითხოვს გაარკვიოს არის თუ არა იგი მიმდებარე მთელი რიცხვების ნაკრები, დაბეჭდე ”დიახ” თუ არის, დაბეჭდე ”არა” თუ არა.

მაგალითი

ნიმუშის შეყვანა:

[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-ზე და ჩვენ გავაგრძელებთ მის გაზრდას შემდეგ ოპერაციებში. იგი შეამოწმებს მთელი რიცხვების მომიჯნავე ნაკრების ზომას, რადგან მას განსხვავებული ზომა ექნება, ვიდრე Set, თუ მასივში არ არის მომიჯნავე მთელი რიცხვები. Arr [0] -1 იქნება მიმდინარეElement- ის მნიშვნელობა. ეს გააკვირვებს კომპლექტს რიცხვები.

გახსენით მარყუჟი და ის გაგრძელდება მანამ, სანამ სეტს არ აქვს მიმდინარეElement, რადგან მარყუჟში ჩვენ ვაპირებთ რაოდენობის რაოდენობის გაზრდას 1-ით (თვლა = რაოდენობა + 1) და ამჟამინდელი ელემენტის მნიშვნელობის შემცირება 1-ით (currentElement = currentElement - 1) მიმდინარეElement- ის მნიშვნელობად დავაყენოთ arr [0] +1 და გახსენით კიდევ ერთი ციკლი და ის გაგრძელდება მანამ, სანამ Set არ შეიცავს currentElement- ს, მაგრამ ამჯერად ჩვენ გავზრდით მნიშვნელობებს 1 რიცხვით ++ და currentElement ++. დაბოლოს, ჩვენ გადავამოწმებთ, არის თუ არა თვლის მნიშვნელობა ტოლი Set- ის ზომის, თუ აღმოჩნდა, რომ ის სიმართლეა, მაშინ true დავაბრუნე, false დავაბრუნო false.

განვიხილოთ მაგალითი:

მაგალითი

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

მასივის გადაკვეთის შემდეგ, Set- ში გვექნება შემდეგი მნიშვნელობები.

უცნობია: {2,3,4,5,6}, რადგან ის შლის დუბლიკატ ელემენტებს

რაოდენობა = 1, მიმდინარეElement = arr [0] -1 = 4;

  • მიუხედავად იმისა, რომ კომპლექტს აქვს მიმდინარეElement (4) სიმართლეა,

ითვლიან = ითვლიან + 1 => ითვლიან = 2, მიმდინარე ელემენტი– => მიმდინარე ელემენტი = 3

  • მიუხედავად იმისა, რომ კომპლექტს აქვს მიმდინარეElement (3) სიმართლეა,

ითვლიან = ითვლიან + 1 => ითვლიან = 3, მიმდინარე ელემენტი– => მიმდინარე ელემენტი = 2

  • მიუხედავად იმისა, რომ კომპლექტს აქვს მიმდინარეElement (2) სიმართლეა,

ითვლიან = ითვლიან + 1 => ითვლიან = 4, მიმდინარე ელემენტი– => მიმდინარე ელემენტი = 1

  • მიუხედავად იმისა, რომ Set– ს აქვს currentElement (1) არასწორია, ამიტომ ის გამოდის ციკლიდან.

დააყენეთ currentElement [0] = arr [0] +1 => currentElement = 6

  • მიუხედავად იმისა, რომ კომპლექტს აქვს მიმდინარეElement (6) სიმართლეა,

თვლა = თვლა + 1 => თვლა = 5, მიმდინარე ელემენტი ++ => მიმდინარე ელემენტი = 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.

ჯავის კოდი, რათა შეამოწმოს, არის თუ არა მასივი მომიჯნავე მთელი რიცხვები, დასაშვებია ეგზემპლარი

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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.