جفتهایی را با مجموع داده شده پیدا کنید که عناصر جفت در ردیفهای مختلف باشند


سطح دشواری متوسط
اغلب در آمازون دی شاو دیرتی خاکستری نارنجی در واقع پینترست داده Teradata
صف مخلوط ماتریس

بیان مسأله

مساله "جفتهایی را با مجموع داده شده پیدا کنید که عناصر جفت در ردیفهای مختلف باشند" بیان می کند که به شما یک ماتریس از اعداد صحیح و مقداری به نام "جمع" داده می شود. دستور مسئله می خواهد همه جفت های ماتریسی را که در یک مقدار معین جمع می شود بنام sum جمع کند و همچنین هر دو عدد باید از یک ردیف متفاوت باشند. (هر دو عدد نباید از یک ردیف باشند).

مثال

int matrix[][]= {{3, 4, 7, 2},

{8, 9, 1, 10},

{5, 4, 0, 4},

{12, 0, 1, 13}};



sum = 15
(3, 12), (7, 8), (2, 13), (10, 5)

توضیح: هر یک از اعداد هر جفت از یک ردیف متفاوت است.

الگوریتم برای یافتن جفتهایی با جمع داده شده به گونه ای که عناصر جفت در ردیف های مختلف قرار داشته باشند

1. Declare a map.
2. Put all the values of the matrix into the map with their row and column index.
3. Traverse the matrix.
  1. Set the remainingValue to the difference of sum and each value of the matrix.
  2. Check if the map contains the value of remainingValue if true then get its row and column index which we already put it into the map.
    1. Check if this row value is not equal to current i and also a row is greater than i.
      1. If true then print the matrix[i][j] and matrix[row][column].
4. Keep repeating the process until the whole matrix is traversed.

توضیح

به ما ماتریسی از اعداد صحیح داده می شود. ما باید تمام جفت ها را در یک ماتریس پیدا کنیم ، به طوری که عنصر هر جفت یک مقدار برابر با مقدار داده شده داشته باشد. و همچنین شرطی داده شده است ، اعدادی که به صورت جفت انتخاب می کنیم باید از ردیف مختلف ماتریس باشند. اگر ما با رویکرد ساده لوحانه به حل آن ادامه دهیم. و هر ردیف را در عنصر رد کنید و سپس O (n) را می گیرد4) ما با استفاده از هش کردن یا نقشه / HashMap. ما نقشه را اعلام خواهیم کرد. شروع به پیمایش ماتریس کرده و عناصر ماتریس را به عنوان کلید در نقشه قرار دهید. و ردیف و ستون عنصر ماتریس آن به عنوان یک مقدار.

می توانیم مقدار شاخص ردیف و ستون را با استفاده از روش make_pair در ++ C در نقشه قرار دهیم. یا اگر از java استفاده می کنیم می توانیم به سادگی یک کلاس ایجاد کنیم و این اشیا class کلاس است که می توانیم آن را در نقشه ذخیره کنیم. بعداً ، اگر مجبور شویم آن مقدار را بدست آوریم ، از آن شی کلاس برای بدست آوردن مقادیر سطر و ستون استفاده خواهیم کرد.

مورد بعدی که ما انجام خواهیم داد عبور از ماتریس است. در یک حلقه تو در تو ، ما هر یک از عناصر ماتریس را برداشته و آن را از مقدار جمع داده شده کسر کرده و متغیری به نام باقی مانده را در آن ذخیره می کنیم و بررسی می کنیم که آیا نقشه در صورت درست بودن این مقدار را دارد یا خیر ، هم عنصر فعلی ماتریس و هم مقدار باقی مانده را جمع می کنیم نباید به یک ردیف تعلق داشته باشد ، اگر همه شرایط درست شد ، عناصر یک جفت را چاپ کرده و برای جستجوی بیشتر ادامه دهید تا از همه جفت ها مطلع شوید. ما مقادیر سطر و ستون آن نقشه را نیز به عنوان شکل شی بدست آورده ایم همانطور که در بالا توضیح دادیم.

جفتهایی را با مجموع داده شده پیدا کنید که عناصر جفت در ردیفهای مختلف باشند

رمز

کد C ++ برای یافتن جفتهایی با جمع داده شده به گونه ای که عناصر جفت در ردیف های مختلف قرار داشته باشند

#include<iostream>
#include<unordered_map>

using namespace std;

const int MAX = 100;

void makePairWithGivenSum (int matrix[][MAX], int n, int sum)
{
    unordered_map<int, pair<int, int> > MAP;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            MAP[matrix[i][j]] = make_pair(i, j);

    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            int remainingSum = sum - matrix[i][j];
            auto it = MAP.find(remainingSum);

            if (it != MAP.end())
            {
                pair<int, int> p = it->second;
                int row = p.first, col = p.second;
                if (row != i && row > i)
                    cout << "(" << matrix[i][j] << ", "
                         << matrix[row][col] << "), ";
            }
        }
    }
}
int main()
{
    int n = 4, sum = 11;
    int matrix[][MAX]= {{3, 4, 7, 2},
        {8, 9, 1, 10},
        {5, 4, 0, 4},
        {12, 0, 1, 13}
    };
    makePairWithGivenSum (matrix, n, sum);
    return 0;
}
(3, 8), (7, 4), (2, 9), (10, 1),

کد جاوا برای یافتن جفتهایی با جمع داده شده به گونه ای که عناصر جفت در ردیف های مختلف قرار داشته باشند

import java.util.HashMap;
class Pair
{
    int first, second;
    Pair(int first, int second)
    {
        this.first=first;
        this.second=second;
    }
}
class pairSum
{
    public static void makePairWithGivenSum(int matrix[][], int n, int sum)
    {
        HashMap<Integer, Pair > MAP=new HashMap<Integer, Pair>();
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                MAP.put(matrix[i][j], new Pair(i,j));
            }
        }
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                int remainingSum = sum - matrix[i][j];

                if (MAP.containsKey(remainingSum))
                {
                    Pair p = MAP.get(remainingSum);
                    int row = p.first, col = p.second;
                    if (row != i && row > i)
                        System.out.print("(" + matrix[i][j] + ", " + matrix[row][col] + "), ");

                }
            }
        }
    }
    public static void main(String [] args)
    {
        int n = 4, sum = 15;
        int matrix[][]= {{3, 4, 7, 2},
            {8, 9, 1, 10},
            {5, 4, 0, 4},
            {12, 0, 1, 13}
        };
        makePairWithGivenSum (matrix, n, sum);
    }
}
(3, 12), (7, 8), (2, 13), (10, 5),

تحلیل پیچیدگی

پیچیدگی زمان

ما در حال مرور ماتریس هستیم و از آنجا که از HashMap استفاده می کنیم ، قادر به دستیابی هستیم بر2جایی که "n" تعداد عناصر ماتریس است.

پیچیدگی فضا

بر) جایی که "N" تعداد عناصر ماتریس است.