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


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית MakeMyTrip Zoho
מערך בליל מִיוּן

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

דוגמה

קלט:

מספרים [] = {12, 10, 9, 45, 2, 10, 10, 45}

פלט:

12, 10, 9, 45, 2

גישה 1: פתרון כוח הברוט

רעיון מרכזי

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

אַלגוֹרִיתְם

  1. הפעל לולאה עבור אני בטווח 0 עד n-1
    1. הפעל לולאה עבור j בטווח 0 עד i
      • אם j == I, הדפס מספרים [i].
      • אם המספרים [i] שווים למספרים [j], פרצו מהלולאה הזו.
    2. לַחֲזוֹר.

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

תוכנית C ++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;i++)
    {
        cin>>nums[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j==i)
            {
                cout<<nums[j]<<" ";
            }
            if(nums[i]==nums[j])
            {
                break;
            }
        }
    }
    return 0;
}
5
3 3 1 2 1
3 1 2

תוכנית JAVA

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++)
        {
            nums[i] = sc.nextInt();;
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(j==i)
                {
                    System.out.print(nums[i]+" ");
                }
                if(nums[i]==nums[j])
                {
                    break;
                }
            }
        }
  }
}

10 
4 6 6 2 6 3 4 2 2 7
4 6 2 3 7

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

מורכבות זמן

יש לנו שתי לולאות מקוננות, כל אחת בגודל n. אז מורכבות הזמן היא O (N ^ 2).

מורכבות בחלל

לא השתמשנו במרחב נוסף ולכן מורכבות הזמן היא O (1).

גישה 2: פתרון מותאם עם Hashing

רעיון מרכזי

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

אַלגוֹרִיתְם

  1. הכריז על שולחן חשיש.
  2. הפעל לולאה עבור אני בטווח 0 עד n-1:
    • אם מספרים [i] אינם קיימים בטבלת החשיש, הדפס אותה והכנס אותה לטבלת החשיש.
    • אם מספרים [i] אינם קיימים בטבלת החשיש, דלג עליה.
  3. לַחֲזוֹר.

לדוגמא, נניח

מספרים [] = {3, 3, 1, 2, 1}

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

השולחן מימין הוא שולחן החשיש.

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

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

תוכנית C ++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;i++)
    {
        cin>>nums[i];
    }
    unordered_set<int> hash_table;
    for(int i=0;i<n;i++)
    {
        if(hash_table.count(nums[i])==0)  //hash_table.count(x) returns 1 if x is present in the hash_table otherwise returns 0
        {
            hash_table.insert(nums[i]);
            cout<<nums[i]<<" ";
        }
    }
    return 0;
}
5
3 3 1 2 1
3 1 2

תוכנית JAVA

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++)
        {
            nums[i] = sc.nextInt();;
        }
        Set<Integer> hash_table = new HashSet<Integer>(); 
        for(int i=0;i<n;i++)
        {
            if(!hash_table.contains(nums[i]))  
            {
                hash_table.add(nums[i]);
                System.out.print(nums[i]+" ");
            }
        }
  }
}

10 
1 2 2 1 3 5 6 3 4 9
1 2 3 5 6 4 9

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

מורכבות זמן

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

מורכבות חלל

לקחנו שולחן חשיש נוסף כך שמורכבות החלל שלנו היא עַל).

הפניות