چیک کریں کہ کیا ارے میں ڈپلیکیٹس کی اجازت کے ساتھ ملحق اجزا شامل ہیں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایکسینچر ایمیزون ہدایت فیس بک Intuit
لڑی ہیش سلک

آپ کو ایک دیا جاتا ہے صف انٹیجرز کا جس میں ڈپلیکیٹ عناصر بھی ہوسکتے ہیں۔ مسئلے کے بیان میں یہ جاننے کے لئے کہ آیا یہ مابعد عددی اعداد و شمار کا ایک سیٹ ہے ، اگر "ہاں" ہے تو پرنٹ کریں ، اگر نہیں ہے تو "نہیں" پرنٹ کریں۔

مثال کے طور پر

نمونہ ان پٹ:

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

نمونہ پیداوار:

جی ہاں

وضاحت:

اس میں تعداد کے متمم اعداد کا ایک مجموعہ ہے [2، 3، 4، 1]

الگورتھم یہ جانچنے کے ل if کہ کیا صف میں ڈپلیکیٹس کی اجازت کے ساتھ ملحق عددی اعداد شامل ہیں

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). کرنٹ ایلیمینٹ کی قدر کو آرر [0] +1 پر سیٹ کریں اور دوسرا لوپ کھولیں اور یہ اس وقت تک جاری رہے گا جب سیٹ میں اس میں کرنٹ ایلیمنٹ موجود نہ ہو ، لیکن اس بار ہم دونوں اقدار کو 1 گنتی ++ اور موجودہ ایلیمینٹ ++ میں بڑھا دیں گے۔ آخر میں ، ہم جانچ پڑتال کریں گے کہ آیا گنتی کی قیمت سیٹ کے سائز کے برابر ہے ، اگر یہ صحیح پایا جاتا ہے تو پھر سچائی کو لوٹائیں۔

آئیے ایک مثال پر غور کریں:

مثال کے طور پر

arr [] = {5، 2، 3، 6، 4، 4، 6، 6}؛

صف کو عبور کرنے کے بعد ، ہمارے پاس سیٹ میں درج ذیل اقدار ہوں گے۔

سیٹ کریں: {2,3,4,5,6،XNUMX،XNUMX،XNUMX،XNUMX. ، کیونکہ یہ نقل عناصر کو ہٹاتا ہے

گنتی = 1 ، موجودہ عنصر = ارر [0] -1 = 4؛

  • جبکہ سیٹ میں موجودہ عنصر (4) درست ہے ،

گنتی = گنتی + 1 => گنتی = 2 ، موجودہئیلمیٹ => کرنٹ ایلیمینٹ = 3

  • جبکہ سیٹ میں موجودہ عنصر (3) درست ہے ،

گنتی = گنتی + 1 => گنتی = 3 ، موجودہئیلمیٹ => کرنٹ ایلیمینٹ = 2

  • جبکہ سیٹ میں موجودہ عنصر (2) درست ہے ،

گنتی = گنتی + 1 => گنتی = 4 ، موجودہئیلمیٹ => کرنٹ ایلیمینٹ = 1

  • جبکہ سیٹ میں کرینٹیلیمنٹ (1) غلط ہے ، لہذا یہ لوپ سے باہر آجاتا ہے۔

موجودہ عنصر [0] = آرر [0] +1 => کرنٹ ایلیمینٹ = 6 سیٹ کریں

  • جبکہ سیٹ میں موجودہ عنصر (6) درست ہے ،

گنتی = گنتی + 1 => گنتی = 5 ، موجودہ + عنصر ++ => کرنٹ ایلیمینٹ = 7

  • جبکہ سیٹ میں کرینٹیلیمنٹ (7) غلط ہے لہذا یہ لوپ سے باہر آتا ہے

اور یہ چیک کرے گا کہ آیا گنتی سیٹ کے سائز کے برابر ہے اور حالت مطمئن ہے تو یہ درست ہو جائے گی اور مرکزی تقریب میں ہاں پرنٹ ہوگی۔

عمل

سی ++ کوڈ یہ چیک کرنے کے ل ar کہ سرے میں ڈپلیکیٹس کی اجازت کے ساتھ ملحق عددی اعداد پر مشتمل ہے یا نہیں

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

جاوا کوڈ یہ چیک کرنے کے ل if کہ سرے میں ڈپلیکیٹس کی اجازت کے ساتھ ملحق عددی اعداد پر مشتمل ہے یا نہیں

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.

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔

خلائی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔