जाँचें कि क्या ऐरे में डुप्लिकेटेड अनुमतियों के साथ समसामयिक पूर्णांक हैं


कठिनाई स्तर मध्यम
में अक्सर पूछा एक्सेंचर वीरांगना डायरेक्टी Facebook सहज
ऐरे हैश तार

आपको एक दिया जाता है सरणी पूर्णांकों में डुप्लिकेट तत्व शामिल हो सकते हैं। समस्या कथन यह पता लगाने के लिए कहता है कि क्या यह सन्निहित पूर्णांक का एक सेट है, यदि "हाँ" प्रिंट है, तो यह "नहीं" प्रिंट करें यदि यह नहीं है।

उदाहरण

नमूना इनपुट:

[३, ४, ६, ५, 2, 3]

नमूना आउटपुट:

हाँ

स्पष्टीकरण:

इसमें संख्या के सन्निहित पूर्णांक का एक सेट है [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 करंट की वैल्यू होगी। इसके सेट पर नजर रखेंगे पूर्णांकों.

एक लूप खोलें और यह तब तक चलता रहेगा जब तक कि सेट में करेंटइलमेंट न हो जाए, क्योंकि एक लूप में हम 1 (काउंट = काउंट + 1) द्वारा काउंट की वैल्यू बढ़ाते जा रहे हैं और करंट वैल्यू को 1 से घटाते जा रहे हैं (करेंट्लीमेंट / करंट क्लीमेंट (1)। CurrentElement का मान सेट करने के लिए [0] +1 को खोलें और एक और लूप खोलें और यह तब तक चलता रहेगा जब तक Set में CurrentElement नहीं होगा, लेकिन इस बार हम दोनों मानों को 1 काउंट ++ और currentElement ++ तक बढ़ाएंगे। अंत में, हम जाँचेंगे कि क्या गणना का मान सेट के आकार के बराबर है, अगर यह सत्य पाया जाता है तो सही लौटाएं अन्यथा गलत है।

चलिए, हम एक उदाहरण पर विचार करते हैं:

उदाहरण

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

सरणी को ट्रेस करने के बाद, हमारे पास सेट में निम्नलिखित मान होंगे।

सेट करें: {2,3,4,5,6}, क्योंकि यह डुप्लिकेट तत्वों को हटाता है

गणना = 1, करंट ईलीमेंट = गिरफ्तारी [0] -1 = 4;

  • जबकि सेट चालू है (4) सच है,

काउंट = काउंट + 1 => काउंट = 2, करंट इलीमेंट- => करंट इलीमेंट = 3

  • जबकि सेट चालू है (3) सच है,

काउंट = काउंट + 1 => काउंट = 3, करंट इलीमेंट- => करंट इलीमेंट = 2

  • जबकि सेट चालू है (2) सच है,

काउंट = काउंट + 1 => काउंट = 4, करंट इलीमेंट- => करंट इलीमेंट = 1

  • जबकि Set में करंट इलीमेंट (1) गलत है, इसलिए यह लूप से बाहर आता है।

करंट इलीमेंट सेट करें [0] = अरेस्ट [0] +1 => करंट इलीमेंट = 6

  • जबकि सेट चालू है (6) सच है,

काउंट = काउंट + 1 => काउंट = 5, करंट इलीमेंट ++ => करंट इलीमेंट = 7

  • जबकि Set में करंट इलीमेंट (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.

जटिलता विश्लेषण

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है।