합이 주어진 값 x와 같은 XNUMX 개의 정렬 된 배열에서 네 배를 계산합니다.

난이도 중급
자주 묻는 질문 수행자 광신자 문 프로그 연구소 Synopsys
배열 이진 검색 해시 수색 정렬조회수 36

문제 정책

문제 "정렬 된 XNUMX 개의 배열에서 주어진 값 x와 같은 합계를 XNUMX 배로 계산"하면 XNUMX 개의 정수 배열과 x라는 값이 주어집니다. 문제 설명은 각 쿼드 러 플렛의 요소 합이 x라고하는 주어진 값과 동일한 덧셈을 가질 수있는 쿼드 러 플렛의 수를 알아 내도록 요청합니다.

int arr1[] = { 2, 5, 6, 9 };

int arr2[] = { 1, 3, 7, 11 };

int arr3[] = { 1, 5, 6, 8 };

int arr4[] = { 2, 3, 5, 10 };

Sum=32
5

설명 : 필요한 값 x = 5를 제공하기 위해 합산 할 수있는 5 개의 XNUMX 개가 있습니다.

 

합계가 x 인 XNUMX 개의 정렬 된 배열에서 XNUMX 배를 계산하는 알고리즘

1. Set the value of count to 0.
2. Declare a map.
3. Traverse the first and second list and store the sum of each pair that can be formed with the two lists into the map along with their frequency.
4, Traverse the other two arrays.
    1. Pick a sum of each pair from the two arrays and check if the x-sum is present in a map.
        1. If present then gets their frequency and add it to the value of count.
5. Return count.

설명

XNUMX 개의 정수 배열과 숫자 x를 제공했습니다. 우리의 임무는 x와 같은 형성 될 수있는 총 XNUMX 중의 수를 찾는 것입니다. 이를 위해 우리는 해싱. 우리는 지도 이를 위해 이러한 방식으로이 문제를 해결할 수있는 효율적인 접근 방식을 제공 할 것입니다.

카운트 값을 0으로 설정하면이 카운트 변수는 쿼드 러 플렛의 수를 저장할 것입니다. 지도를 선언하겠습니다. 처음 두 배열을 순회하기 시작하고 처음 두 배열의 각 쌍의 합계를 키로 맵에 저장하고 각 합계의 빈도를 키 값으로 맵에 넣습니다. 비슷한 값의 다른 쌍을 찾으면 합계. 합계의 빈도 값을 늘립니다. 처음 두 배열을 완전히 순회 한 후 처음 두 배열에서 쌍의 합을 얻습니다.

이제 우리는 또 다른 두 배열 순회를 진행할 것입니다. 배열에서 각 쌍의 두 요소의 합을 선택합니다. 한 배열의 숫자와 다른 배열의 숫자. 그런 다음 x의 차이와이 쌍의 합이 맵에 있는지 확인합니다. 그런 다음지도에서 해당 쌍의 빈도를 가져옵니다. 존재하는 경우 해당 주파수를 카운트에 추가하여 카운트 값을 증가시킬 것입니다. 이는 모든 배열에서 하나의 쿼드 러 플렛을 찾았 음을 의미합니다. 왜냐하면 우리가 10 + 20 = 30이면 30-10이이 솔루션에 유사한 일이 일어나고 마침내 count의 값을 반환하기 때문에 값 중 하나를 찾을 수 있기 때문입니다.

합이 주어진 값 x와 같은 XNUMX 개의 정렬 된 배열에서 네 배를 계산합니다.

암호

합이 주어진 값 x와 같은 XNUMX 개의 정렬 된 배열에서 XNUMX 배를 계산하는 C ++ 코드

#include <iostream>
#include<unordered_map>

using namespace std;

int getNumberOfQuadruples(int arr1[], int arr2[], int arr3[],int arr4[], int n, int x)
{
    int count = 0;

    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            MAP [arr1[i] + arr2[j]]++;

    for (int k = 0; k < n; k++)
        for (int l = 0; l < n; l++)
        {
            int p_sum = arr3[k] + arr4[l];

            if (MAP.find(x - p_sum) != MAP.end())
                count += MAP [x - p_sum];
        }

    return count;
}
int main()
{
    int arr1[] = { 2, 5, 6, 9 };
    int arr2[] = { 1, 3, 7, 11 };
    int arr3[] = { 1, 5, 6, 8 };
    int arr4[] = { 2, 3, 5, 10 };

    int n = sizeof(arr1) / sizeof(arr1[0]);
    int x = 32;
    cout << "Count = "<< getNumberOfQuadruples (arr1, arr2, arr3, arr4, n, x);
    return 0;
}
Count = 3

합계가 주어진 값 x와 같은 XNUMX 개의 정렬 된 배열에서 XNUMX 배를 계산하는 Java 코드

import java.util.HashMap;

class QuadrupletsSum
{
    public static int getNumberOfQuadruples (int arr1[], int arr2[], int arr3[], int arr4[], int n, int x)
    {
        int count = 0;

        HashMap<Integer,Integer> MAP = new HashMap<>();

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if(MAP.containsKey(arr1[i] + arr2[j]))
                    MAP.put((arr1[i] + arr2[j]), MAP.get((arr1[i] + arr2[j]))+1);
                else
                    MAP.put((arr1[i] + arr2[j]), 1);

        for (int k = 0; k < n; k++)
            for (int l = 0; l < n; l++)
            {
                int p_sum = arr3[k] + arr4[l];

                if (MAP.containsKey(x - p_sum))
                    count += MAP.get(x - p_sum);
            }

        return count;
    }
    public static void main(String[] args)
    {
        int arr1[] = { 2, 5, 6, 9 };
        int arr2[] = { 1, 3, 7, 11 };
        int arr3[] = { 1, 5, 6, 8 };
        int arr4[] = { 2, 3, 5, 10 };

        int n = arr1.length;
        int x = 32;
        System.out.println("Count = "
                           + getNumberOfQuadruples (arr1, arr2, arr3, arr4, n, x));
    }
}
Count = 3

복잡성 분석

시간 복잡성

의 위에2어디에 "엔" 배열의 요소 수입니다. 우리는 매번 두 배열의 요소 만 순회했기 때문에 N ^ 2의 다항식 시간 복잡도를 얻었습니다.

공간 복잡성

의 위에2어디에 "엔" 배열의 요소 수입니다. HashMap에 저장되는 요소의 수는 두 배열의 요소가됩니다. 우리는 XNUMX 차 공간 복잡성을 달성합니다.

Translate »