주어진 합계로 쌍 계산

난이도 쉽게
자주 묻는 질문 수행자 아마존 팩트 셋 인상
배열 해시 수학 정렬조회수 138

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

정수가 주어짐 정렬 크기가 n이고 정수 'K'인 경우, 합계가 'K'인 배열에 존재하는 쌍의 수 (고유하지 않아도 됨)를 계산해야합니다.

입력:

Arr = {1, 5, 7, 1}

K = 6

출력:

2

주어진 합계를 사용하는 개수 쌍에 대한 무차별 대입 솔루션

주요 아이디어

주어진 배열의 모든 쌍을 반복 한 다음 합이 K 인 쌍을 계산할 수 있습니다.

암호알고리즘

  1. 변수 answer = 0을 초기화합니다.
  2. 0에서 n-1 사이의 I에 대해 루프 실행
    1. i + 1 ~ n-1 범위에서 j에 대해 루프를 실행합니다.
      1. arr [i] + arr [j]가 k와 같으면 1 씩 답답합니다.
  3. 답변을 반환합니다.

실시

C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]+a[j]==k){
                ans++;
            }
        }
    }
    cout<<"Number of pairs with the given sum are: "<<ans;
}
4 6
1  5  7 1
Number of pairs with the given sum are: 2

JAVA 프로그램

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(a[i]+a[j]==k){
                    ans++;
                }
            }
        }
    System.out.println("Number of pairs with the given sum are: "+ans);
  }
}

6 4
2 2 3 1 1 5
Number of pairs with the given sum are: 3

주어진 합계를 사용하는 개수 쌍에 대한 복잡성 분석

시간 복잡성

모든 쌍을 반복하고 대략 N ^ 2 쌍이 있으므로 총 시간 복잡도는 O (N ^ 2)입니다.

공간 복잡성

추가 공간을 사용하지 않았으므로 공간 복잡성은 O (1)입니다.

주어진 합계를 사용하는 개수 쌍에 대한 해싱 개념

주요 아이디어

주어진 배열에있는 각 숫자의 빈도를 저장할 해시 테이블을 유지합니다.

이제 배열을 반복하고 값이 k-arr [i]와 같은 모든 요소를 ​​추가합니다.

하지만 한 가지 조건을 확인해야합니다.

arr [i]가 k-arr [i]와 같다면, 우리는 별개의 쌍을 찾아야하기 때문에 답에서 1을 뺄 것입니다. 그래서 우리는 쌍에 대해 arr [i]를 두 번 취할 수 없습니다. 이것이 우리가 이것을 빼는 이유입니다 우리의 대답에서 케이스.

암호알고리즘

  1. 배열에있는 각 요소의 개수를 저장할 해시 테이블을 만듭니다.
  2. 범위 0에서 n-1까지 I에 대한 배열을 반복합니다.
    1. arr [i]가 k-arr [i]와 같으면 (count_of (k-arr [i])-1)을 답에 추가합니다.
    2. arr [i]가 k-arr [i]와 같지 않으면 답에 (count_of (k-arr [i])를 추가합니다.
  3. 답변을 반환합니다.

어레이 = {1, 2, 3, 3, 4, 1, 1}에 대해 생성 된 해시 테이블은 다음과 같습니다.

주어진 합계로 쌍 계산

실시

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> fre;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        fre[arr[i]]++;
    }
    int answer = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == k - arr[i])
        {
            answer += (fre[arr[i]] - 1);
        }
        else
        {
            answer += (fre[k - arr[i]]);
        }
    }
    answer /= 2;
    cout << "Number of pairs with the given sum are: "<<answer << endl;
    return 0;
}
6 4
1 2 2 2 3 4
Number of pairs with the given sum are: 4

JAVA 프로그램

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        HashMap<Integer, Integer> fre = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            Integer j = fre.get(arr[i]); 
            fre.put(arr[i], (j == null) ? 1 : j + 1); 
        }
        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == k - arr[i])
            {
                answer += (fre.get(arr[i]) - 1);
            }
            else
            {
                Integer j = fre.get(k - arr[i]); 
                if(j!=null)
                    answer += j;
            }
        }
        answer /= 2;
    System.out.println("Number of pairs with the given sum are: "+answer);
  }
}

6 7
3 5 6 1 4 4
Number of pairs with the given sum are: 3

주어진 합계를 사용하는 개수 쌍에 대한 복잡성 분석

시간 복잡성

배열을 한 번만 반복하므로 시간 복잡도는 O (N)입니다.

공간 복잡성

해시 테이블을 유지하고 있으므로 공간 복잡성은 O (N)입니다.

참조

균열 시스템 설계 인터뷰
Translate »