쌍의 요소가 다른 행에 있도록 주어진 합계로 쌍을 찾습니다.


난이도 중급
자주 묻는 질문 아마존 DE Shaw Directi 그레이 오렌지 과연 클립 테라 데이타
배열 해시 매트릭스

문제 정책

“쌍의 요소가 서로 다른 행에 있도록 주어진 합계로 쌍을 찾으십시오.”문제는 정수 행렬과“합계”라는 값이 제공된다는 것을 나타냅니다. 문제 설명은 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 (n4). 해싱 또는 지도 / HashMap. 우리는지도를 선언 할 것입니다. 행렬 순회를 시작하고 행렬의 요소를 맵에 키로 넣습니다. 그리고 행렬 요소의 행 및 열 인덱스를 값으로 사용합니다.

C ++에서 make_pair 메소드를 사용하여 행과 열 인덱스의 값을 맵에 넣을 수 있습니다. 또는 Java를 사용하는 경우 단순히 클래스를 생성 할 수 있으며 그 클래스 객체를 맵에 저장할 수 있습니다. 나중에 해당 값을 가져와야하는 경우 해당 클래스 개체를 사용하여 해당 행 및 열 값을 가져옵니다.

다음으로 할 일은 행렬을 순회하는 것입니다. 중첩 된 루프에서 행렬의 각 요소를 선택하여 주어진 합계 값에서 빼고 해당 값을 leftSum이라는 변수에 저장하고 맵에이 값이 참이면이 값이 포함되어 있는지 확인한 다음 행렬의 현재 요소와 leftSum을 모두 확인합니다. 동일한 행에 속하지 않아야합니다. 모든 조건이 참이되면 한 쌍의 요소를 인쇄하고 추가 순회를 진행하여 모든 쌍을 찾습니다. 또한 설명에서 위에서 언급했듯이 해당 맵의 행 및 열 값을 개체 형식으로 얻었습니다.

쌍의 요소가 다른 행에 있도록 주어진 합계로 쌍을 찾습니다.

암호

쌍의 요소가 서로 다른 행에 있도록 주어진 합계로 쌍을 찾는 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을 사용하고 있기 때문에 의 위에2어디에 "엔" 행렬의 요소 수입니다.

공간 복잡성

의 위에) 어디에 "엔" 행렬의 요소 수입니다.