چيڪ ڪريو جيڪڏهن آرري اجازت ڏنل انگن اکرن تي مشتمل آهي


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Accenture Amazon سڌو ڪريو سائنسي
ڪيريو هاش اسٽرنگ

توھان کي ھڪڙو ڏنو وڃي ٿو صف انٽيگرز جن ۾ ڊپلائيٽ عناصر پڻ شامل هجن. مسئلي جو بيان اهو ڳولڻ جي لاءِ پڇان ٿو ته ڇا اهو ڇانيل انٽيگرز جو سيٽ آهي ، جيڪڏهن هو نه پر پرنٽ “ها” پرنٽ ڪريو.

مثال

نموني انپٽ:

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

وضاحت

اسان کي هڪ سوال ڏنو ويو آهي اهو طئي ڪرڻ لاءِ ته جيڪڏهن ڏنل سيٽ جو هڪ سيٽ آهي لاڳيتو انٽيگرز جيڪڏهن اهو پرنٽ ڪري چڪو آهي ها ٻيو پرنٽ نمبر اسان استعمال ڪرڻ وارا آهيون مقرر جئين اهو تمام نقلي عنصرن کي هٽائڻ ۽ پنهنجو ڪم آسان بڻائي ڇڏيندي آهي. سيٽ هڪ مستقبل فراهم ڪري ٿو جيڪڏهن ان جا ڪيترائي عنصر آهن جن ۾ ڪجهه نقل وارا عنصر آهن. پوءِ اهو هلڻو آهي سمورا نقل ڪ andڻ ۽ ان ۾ فقط ڌار عنصر شامل آهن.

اسان صف کي آرائين ڪري تمام عناصر داخل ڪرڻ وارا آهيون مقرر ۽ ان ۾ هينئر الڳ عنصر هوندا. 1 جي ڳڻپ جو قدر مقرر ڪريو ۽ اسان انهي کي بعد ۾ آپريشن جاري رکنداسين. اهو انٽيگرن جي برابر سيٽ جو سائز چيڪ ڪندو ڇو ته اهو سيٽ کان مختلف سائيز هوندو جيڪڏهن صف ۾ موجود نهايت صحيح انگ موجود نه آهن. آر آر [0] -1 موجوده ايليمينٽ جو قدر هوندو. اهو سيٽ تي نظر رکندو جيتريون.

هڪ لوپ کوليو ۽ اهو هلندو رهندو جيستائين سيٽ هن ۾ CurrentElement آهي ، ڇاڪاڻ ته هڪ لوپ ۾ اسين ڳڻپ جي قيمت کي 1 (شمار ​​= شمار + 1) ۽ موجوده ايليمنٽ جي قيمت کي 1 مان گهٽائي رهيا آهيون (currentElement = currentElement - 1). currentElement جي قيمت کي ترتيب ڏيو arr [0] +1 ۽ هڪ ٻيو لوپ کوليو ۽ اهو به هلندو رهندو جيستائين سيٽ کي موجودهElement انهي ۾ آهي ، پر هن وقت اسان ٻنهي قدرن کي 1 ڳڻپ ++ ۽ currentElement ++ ذريعي وڌائينداسين. آخر ۾ ، اسان چيڪ ڪنداسون ته ڳڻپ جي قيمت سيٽ جي برابر جي برابر آهي ، جيڪڏهن اها صحيح لڳي ٿي ته پوءِ صحيح موٽي وڃي موٽايو ته غلط آهي.

اچو ته هڪ مثال تي غور ڪريون.

مثال

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

صفن جي پيچراڻ کان پوءِ ، اسان کي سيٽ ۾ هيٺين قيمتون هونديون.

سيٽ ڪريو: {2,3,4,5,6،XNUMX،XNUMX،XNUMX،XNUMX} ، جيئن تہ نقل ڪندڙ عنصر خارج ڪري ڇڏي

ڳڻپ = 1 ، currentElement = arr [0] -1 = 4 ؛

  • جڏهن ته سيٽ موجوده ايليمينٽ آهي (4) سچ آهي ،

ڳڻپ = ڳڻپ + 1 => ڳڻت = 2 ، currentElement– => currentElement = 3

  • جڏهن ته سيٽ موجوده ايليمينٽ آهي (3) سچ آهي ،

ڳڻپ = ڳڻپ + 1 => ڳڻت = 3 ، currentElement– => currentElement = 2

  • جڏهن ته سيٽ موجوده ايليمينٽ آهي (2) سچ آهي ،

ڳڻپ = ڳڻپ + 1 => ڳڻت = 4 ، currentElement– => currentElement = 1

  • جڏهن ته سيٽ موجوده ايليمنٽ (1) غلط آهي ، ان ڪري اها لاپ مان نڪرندي آهي.

سيٽ ڪريو موجوده عنصر [0] = arr [0] +1 => currentElement = 6

  • جڏهن ته سيٽ موجوده ايليمينٽ آهي (6) سچ آهي ،

ڳڻپ = ڳڻپ + 1 => ڳڻتيو = 5 ، موجوده ايليمينٽ ++ => هاڻوڪو عنصر = 7

  • جڏهن ته سيٽ موجوده ايليمنٽ (7) غلط آهي ان ڪري اهو لوپ مان نڪرندو آهي

۽ اهو جانچ ڪندو ته ڇا سيٽ سيٽ جي سائيز برابر آهي ۽ حالت مطمئن آهي تنهن ڪري اهو صحيح واپس اچي ويندو ۽ مرڪزي فنڪشن ۾ ها پرنٽ ڪيو ويندو.

تي عملدرآمد

سي ++ ڪوڊ اهو چيڪ ڪرڻ لاءِ ته ڇا صفن ۾ اجازت ڏنل ٻٻر سان گڏ نقل ٿيل اجازت ڏنل آهن

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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.

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

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.