Хосын элементүүд өөр өөр эгнээнд байхаар өгөгдсөн нийлбэртэй хосыг ол


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны DE Шоу Directi Саарал улбар шар Үнэндээ Pinterest Teradata
Array Хаш матриц

Асуудлын мэдэгдэл

“Өгөгдсөн нийлбэртэй хосыг хосуудын элемент өөр өөр эгнээнд байхаар олоорой” гэсэн бодлогын дагуу танд бүхэл тоон матриц болон “нийлбэр” гэсэн утга өгөгдөнө. Бодлогын даалгавар нь өгөгдсөн утгыг нийлбэр гэж нэрлэдэг матрицын бүх хосыг олохыг хүсэж байгаа бөгөөд тоо нь хоёулаа өөр мөрөөс байх ёстой. (Хоёр тоо хоёулаа нэг эгнээнээс байж болохгүй).

Жишээ нь

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 ашиглаж байгаа бол ердөө л класс үүсгэх боломжтой бөгөөд энэ нь ангийн объект болох газрын зураг дээр хадгалах боломжтой. Дараа нь хэрэв бид энэ утгыг авах шаардлагатай бол тухайн мөрийн баганын утгыг авахын тулд тухайн ангийн объектыг ашиглах болно.

Дараагийн хийх зүйл бол матрицыг туулах явдал юм. Үүрлэсэн гогцоонд бид матрицын элемент бүрийг сонгож өгөгдсөн нийлбэр утгаас хасаад үлдсэнSum нэртэй хувьсагчийг хадгалж, хэрэв газрын зураг энэ утгыг агуулсан бол үнэн бол матрицын одоогийн элемент ба үлдсэн сум хоёулаа шалгана. нэг мөрөнд хамаарахгүй байх ёстой, хэрэв бүх нөхцөл үнэн болох юм бол хосын элементүүдийг хэвлээд цааш үргэлжлүүлэн бүх хосыг олж мэдээрэй. Дээрх тайлбар дээр дурдсанчлан бид газрын зургийн мөр, баганын утгыг объект хэлбэрээр авсан болно.

Хосын элементүүд өөр өөр эгнээнд байхаар өгөгдсөн нийлбэртэй хосыг ол

код

Хосуудын элементүүд өөр өөр эгнээнд байхаар өгөгдсөн нийлбэртэй хосуудыг олох 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),

Өгөгдсөн нийлбэртэй хосыг олохын тулд Java код нь хосын элементүүд өөр өөр эгнээнд байрладаг

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-ийг ашиглаж байгаа тул амжилтанд хүрч чадаж байна O (n2хаана "N" матриц дахь элементүүдийн тоо юм.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" матриц дахь элементүүдийн тоо юм.