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


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

הצהרת בעיה

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

דוגמה

arr[] = {2,6,9,3,1,9,1}
9

הסבר: במערך הנתון ישנם שני מספרים שחוזרים על עצמם אך החזרה הראשונה היא 9.

arr[] = {1,4,7,0,2,5}
No repeating number.

הסבר: במערך הנתון אין מספר חוזר.

אלגוריתם למצוא דמות חוזרת ראשונה

1. Set flag to -1.
2. Declare a Set.
3. Start traversing the array from the right to left.
    1. If the number is repeating then update the value of flag to the index of the current array element.
    2. Else, insert the each array’s element into the declared set.
4. Check if flag value is still -1, then we have found no repeating element.
5. Else print flag index position of array.

הסבר

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

 

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

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

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

קופונים

קוד C ++ למציאת דמות חוזרת ראשונה

#include<bits/stdc++.h>

using namespace std;

void getFirstRepeatedElement(int arr[], int n)
{
    int Flag = -1;

    unordered_set<int> SET;

    for (int i = n - 1; i >= 0; i--)
    {
        if (SET.find(arr[i]) != SET.end())
            Flag = i;

        else
            SET.insert(arr[i]);
    }
    if (Flag!= -1)
        cout << "The first repeating element is " << arr[Flag];
    else
        cout << "There are no repeating elements";
}
int main()
{
    int arr[] = {2,6,9,3,1,9,1};

    int n = sizeof(arr) / sizeof(arr[0]);
    getFirstRepeatedElement (arr, n);
}
The first repeating element is 9

קוד Java כדי למצוא דמות חוזרת ראשונה

import java.util.HashSet;

class FirstRepeatingElement
{
    public static void getFirstRepeatedElement (int arr[])
    {
        int Flag = -1;

        HashSet<Integer> SET = new HashSet<>();

        for (int i=arr.length-1; i>=0; i--)
        {
            if (SET.contains(arr[i]))
                Flag = i;

            else
                SET.add(arr[i]);
        }
        if (Flag!= -1)
            System.out.println("First repeating element is " + arr[Flag]);
        else
            System.out.println("No repeated element");
    }
    public static void main (String[] args)
    {
        int arr[] = {2,6,9,3,1,9,1};
        getFirstRepeatedElement(arr);
    }
}
First repeating element is 9

ניתוח מורכבות

מורכבות זמן

O (n) איפה "N" הוא מספר האלמנטים במערך. מכיוון שאנו משתמשים ב- HashSet, אנו יכולים לבצע הכנסה וחיפוש בפעולות O (1).

מורכבות בחלל

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