זוג ערכים שליליים חיוביים במערך


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית בלזבר Honeywell Hulu Nvidia רובין הוד לילל
מערך בליל

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

דוגמה

קלט:

A[]={2, 3, -1, -2, 9, 1}

פלט:

Pairs having positive value and negative in the array are: -2 2 -1 1

גישה 1: כוח אכזרי

עבור כל רכיב A [i] במערך הקלט, בדוק אם –A [i] קיים במערך עם אינדקס גדול ממני אם קיים, ואז מדפיס זוג זה.

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

  1. הפעל לולאה עבור אני בטווח 0 עד n-1
    1. הפעל לולאה עבור j בטווח i + 1 עד n-1
      1. אם A [i] שווה ל- A [j], הדפס זוג זה.
    2. לַחֲזוֹר.

תוכנית C ++ למציאת זוג ערכים שליליים חיוביים במערך

#include <bits/stdc++.h>
using namespace std;
void printPairs(vector<int> &A)
{
    int n = A.size();
    cout << "Pairs having positive value and negative in the array are: ";
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (A[i] == -A[j])
            {
                if (A[i] <= 0)
                {
                    cout << A[i] << " " << (-A[i]) << " ";
                }
                else
                {
                    cout << (-A[i]) << " " << A[i] << " ";
                }
            }
        }
    }
    cout << endl;
    return;
}
int main()
{
    vector<int> A = {2, 3, -1, -2, 9, 1};
    printPairs(A);
    return 0;
}
Pairs having positive value and negative in the array are: -2 2 -1 1

תוכנית JAVA למציאת זוג ערכים שליליים חיוביים במערך

public class Main
{
    static void printPairs(int[] A)
    {
        int n = A.length;
        System.out.print("Pairs having positive value and negative in the array are: ");
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (A[i] == -A[j])
                {
                    if (A[i] <= 0)
                    {
                       A[i]=-A[i];
                    }
                    System.out.print(A[i]+" -"+A[i]+" ");
                }
            }
        }
        return;
    }
  public static void main(String[] args) {
    int[] A={2, 3, -1, -2, 9, 1};
    printPairs(A);
  }
}
Pairs having positive value and negative in the array are: 2 -2 1 -1

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

מורכבות זמן

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

מורכבות חלל

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

גישה 2: שימוש ב- hashing

רעיון מרכזי

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

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

  1. אתחל טבלת חשיש.
  2. אחסן את התדירות של כל אלמנט בטבלת החשיש.
  3. הפעל לולאה עבור אני בטווח 0 עד n-1
    1. אם –A [i] יש ערך 1 בטבלת החשיש, הדפס זוג זה והוריד את הערך A [i] ו- –A [i] ב -1.

להבין עם דוגמה

ניקח מערך קלט A [] = {2, 3, -1, -2, 9, 1}

אז טבלת החשיש שלנו נראית כך:

זוג ערכים שליליים חיוביים במערך

עכשיו נבצע איטרציה של המערך,

הצבע הכתום מראה את האינדקס הנוכחי,

זוג ערכים שליליים חיוביים במערך זוג ערכים שליליים חיוביים במערך

זוג ערכים שליליים חיוביים במערך

אז התפוקה הסופית היא: -2 2 -1 1

תוכנית C ++ למציאת זוג ערכים שליליים חיוביים במערך

#include <bits/stdc++.h>
using namespace std;
void printPairs(vector<int> &A)
{
    int n = A.size();
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    cout << "Pairs having positive value and negative in the array are: ";
    for (int i = 0; i < n; i++)
    {
        if (hash_table[-A[i]] == 1)
        {
            if (A[i] <= 0)
            {
                cout << A[i] << " " << (-A[i]) << " ";
            }
            else
            {
                cout << (-A[i]) << " " << A[i] << " ";
            }
            hash_table[A[i]]--;
            hash_table[-A[i]]--;
        }
    }
    cout << endl;
    return;
}
int main()
{
    vector<int> A = {2, 3, -1, -2, 9, 1};
    printPairs(A);
    return 0;
}
Pairs having positive value and negative in the array are: -2 2 -1 1

תוכנית JAVA למציאת זוג ערכים שליליים חיוביים במערך

import java.util.*; 
public class Main
{
    static void printPairs(int[] A)
    {
        int n = A.length;
        HashMap<Integer,Integer> hash_table = new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++)
        {
            hash_table.put(A[i],1);
        }
        System.out.print("Pairs having positive value and negative in the array are: ");
        for (int i = 0; i < n; i++)
        {
            if(hash_table.containsKey(-1*A[i]) && hash_table.get(-1*A[i])==1)
            {
                if (A[i] <= 0)
                {
                    A[i]*=-1;
                }
                System.out.print(A[i]+" -"+A[i]+" ");
                hash_table.put(A[i],0);
                hash_table.put(-1*A[i],0);
            }
        }
        return;
    }
  public static void main(String[] args) {
    int[] A={2, 3, -1, -2, 9, 1};
    printPairs(A);
  }
}
Pairs having positive value and negative in the array are: -2 2 -1 1

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

מורכבות זמן

אנו משחזרים את כל המערך פעמיים, כך שמורכבות הזמן היא עַל).

מורכבות חלל

אנו משתמשים בטבלת חשיש, ולכן מורכבות החלל היא עַל).

הפניות