בדוק אם מערך מכיל מספרים שלמים רצופים עם כפילויות מותרות


רמת קושי בינוני
נשאל לעתים קרובות אקסנצ'ר אמזון בעברית דירקטי פייסבוק אינטואיט
מערך בליל מחרוזת

נותנים לך מערך של מספרים שלמים שיכולים להכיל גם אלמנטים כפולים. הצהרת הבעיה מבקשת לברר אם מדובר בקבוצה של מספרים שלמים רצופים, הדפיסו "כן" אם כן, והדפיסו "לא" אם לא.

דוגמה

קלט לדוגמא:

[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 יהיה הערך של currentElement. זה יפקח עין על הסט של מספרים שלמים.

פתח לולאה והיא תמשיך עד שהסט מכיל את הנוכחי הנוכחי, מכיוון שבלולאה אנו הולכים להגדיל את ערך הספירה ב- 1 (ספירה = ספירה + 1) ולהקטין את הערך currentElement ב -1 (currentElement = currentElement - 1). הגדר את הערך של currentElement ל- arr [0] +1 ופתח עוד לולאה והיא גם תמשיך עד שה- Set מכיל את CurrentElement, אך הפעם נגדיל את שני הערכים ב- 1 count ++ ו- currentElement ++. לבסוף, נבדוק אם ערך הספירה שווה לגודל הסט, אם נמצא שהוא נכון ואז להחזיר נכון אחר להחזיר שקר.

הבה נבחן דוגמה:

דוגמה

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

לאחר חציית המערך, נקבל את הערכים הבאים בערכה.

סט: {2,3,4,5,6}, מכיוון שהוא מסיר אלמנטים כפולים

ספירה = 1, currentElement = arr [0] -1 = 4;

  • אמנם לסט יש currentElement (4) נכון,

ספירה = ספירה + 1 => ספירה = 2, currentElement– => currentElement = 3

  • אמנם לסט יש currentElement (3) נכון,

ספירה = ספירה + 1 => ספירה = 3, currentElement– => currentElement = 2

  • אמנם לסט יש currentElement (2) נכון,

ספירה = ספירה + 1 => ספירה = 4, currentElement– => currentElement = 1

  • בעוד שלסט יש currentElement (1) הוא שקר, אז זה יוצא מהלולאה.

הגדר currentElement [0] = arr [0] +1 => currentElement = 6

  • אמנם לסט יש currentElement (6) נכון,

ספירה = ספירה + 1 => ספירה = 5, currentElement ++ => currentElement = 7

  • בעוד שלסט יש 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" הוא מספר האלמנטים במערך.

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך.