ڏنل رقم سان جوڑوں ڳوليو ته جيئن جوڙا جا عنصر مختلف قطار ۾ هجن


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ڊي شاه سڌو گرين اورنج يقينا Pinterest ٽراداتا
ڪيريو هاش قائم ٿينديون

مسئلي جو بيان

"ڏنل رقم سان جوڑوں ڳوليو ته جيئن جوڙا مختلف قطار ۾ هجن" مسئلو ٻڌائي ٿو ته توهان کي انٽيگرس جو هڪ ميٽرڪس ڏنو ويو آهي ۽ قيمت "سم“ سڏجي ٿي. مسئلو بيان ڪري ٿو ته ميٽرڪس ۾ سڀني ڀاڙين کي ڳوليو ، جيڪي ڏنل قيمت تي ڏنل رقم هجي ۽ ٻنهي جا نمبر به هڪ مختلف قطار مان هجن. (ٻنهي جو تعداد هڪ ئي قطار مان نه هئڻ گهرجي).

مثال

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). اسان ان کي حل ڪندي يا هشنگ استعمال ڪندي نقشو / هش ميپ. اسان نقشي جو اعلان ڪنداسين. ميٽرڪس جي پيچيدگي شروع ڪريو ، ۽ ميٽرڪس جي عنصرن کي ڪلي ۾ نقشي ۾ وجهي ڇڏيو. ۽ هن جي ميٽرڪس عنصر جي قطار ۽ ڪالم انڊيڪس هڪ قدر طور.

اسان C ++ ۾ make_pair طريقو استعمال ڪندي نقشي ۾ قطار ۽ ڪالم انڊيڪس جي قيمت رکون ٿا. يا جيڪڏهن اسان جاوا استعمال ڪري رهيا آهيون اسان بس هڪ ڪلاس ٺاهي سگهون ٿا ۽ اهو ڪلاس شيون آهي اسان ان کي نقشي ۾ محفوظ ڪري سگهون ٿا. بعد ۾ ، جيڪڏهن اسان کي انهي قيمت حاصل ڪرڻي پوندي ته اسان اهي ڪلاس شي ۽ قطار ۽ قدر حاصل ڪرڻ لاءِ استعمال ڪنداسين.

ايندڙ ڪم جيڪو اسان ڪندي ڪيو ويندو ميٽرڪس جي موڙ تي چڙهڻ آهي. هڪ بند ٿيل لوپ ۾ ، اسان ميٽرڪس جي هر عنصر کي چونڊينداسين ۽ ڏنل ڏنل قيمت مان ڪٽينداسين ۽ باقي سم نالي ته متغير کي ذخيرو ڪنداسين ۽ چڪاس ڪريو ته نقشي ۾ اها قيمت موجود آهي جيڪڏهن صحيح آهي ته پوءِ ميٽرڪس جي موجوده عنصر ۽ ٻئي جي چڪاس ڪريو. هڪ ئي قطار سان واسطو نه رکڻ گهرجي ، جيڪڏهن سڀني جي حالت صحيح ٿي وڃي ته پوءِ هڪ جوڙي جا عنصر پرنٽ ڪريو ۽ اڳتي وڌڻ جي لاءِ اڳتي وڌڻ لاءِ سڀ جوڙا ڳوليو. اسان اهو نقشو جي قطار ۽ ڪالمن جا قدر پڻ طور فارم طور حاصل ڪيا هئا جئين اسان وضاحت ۾ مٿي ذڪر ڪيو آهي.

ڏنل رقم سان جوڑوں ڳوليو ته جيئن جوڙا جا عنصر مختلف قطار ۾ هجن

ڪوڊ

سي ++ ڪوڊ ڏنل رقم سان جوڙا ڳولڻ لاءِ ته جيئن جوڙا جا عنصر مختلف قطار ۾ هجن

#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),

پيچيدگي تجزيي

وقت جي پيچيدگي

اسان ميٽرڪس مان گذري رهيا آهيون ۽ جڏهن ته اسان هاشميپ استعمال ڪري رهيا آهيون ، اسان حاصل ڪرڻ جي قابل آهيون اي (اين2جتي “ن” ميٽرڪس ۾ عنصرن جو تعداد آهي.

خلائي پيچيدگي

اي (اين) جتي "ن" ميٽرڪس ۾ عنصرن جو تعداد آهي.