배열의 양의 음수 값 쌍

난이도 쉽게
자주 묻는 질문 아마존 벨자바르 하니웰 훌루 엔비디아 Robinhood 큰소리로 말하다
배열 해시조회수 79

한 쌍의 양수 음수 값 정렬 문제 우리는 고유 한 정수의 배열 A를 제공했습니다. 배열에 존재하는 숫자의 양수 값과 음수 값을 가진 모든 쌍을 인쇄하십시오. 발생 순서대로 쌍을 인쇄해야합니다. 요소가 먼저 나타나는 쌍을 먼저 인쇄해야합니다.

입력:

A[]={2, 3, -1, -2, 9, 1}

출력:

Pairs having positive value and negative in the array are: -2 2 -1 1

접근 방식 1 : 무차별 대입

입력 배열의 모든 요소 A [i]에 대해 인덱스가 I보다 큰 배열에 –A [i]가 있는지 확인한 다음이 쌍을 인쇄합니다.

암호알고리즘

  1. 0에서 n-1 사이의 I에 대해 루프 실행
    1. i + 1 ~ n-1 범위에서 j에 대해 루프 실행
      1. A [i]가 -A [j]와 같으면이 쌍을 인쇄합니다.
    2. 반환.

배열에서 양의 음수 값 쌍을 찾기위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
void printPairs(vector<int> &A)
{
    int n = A.size();
    cout << "Pairs having positive value and negative in the array are: ";
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (A[i] == -A[j])
            {
                if (A[i] <= 0)
                {
                    cout << A[i] << " " << (-A[i]) << " ";
                }
                else
                {
                    cout << (-A[i]) << " " << A[i] << " ";
                }
            }
        }
    }
    cout << endl;
    return;
}
int main()
{
    vector<int> A = {2, 3, -1, -2, 9, 1};
    printPairs(A);
    return 0;
}
Pairs having positive value and negative in the array are: -2 2 -1 1

배열에서 양의 음수 쌍을 찾는 JAVA 프로그램

public class Main
{
    static void printPairs(int[] A)
    {
        int n = A.length;
        System.out.print("Pairs having positive value and negative in the array are: ");
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (A[i] == -A[j])
                {
                    if (A[i] <= 0)
                    {
                       A[i]=-A[i];
                    }
                    System.out.print(A[i]+" -"+A[i]+" ");
                }
            }
        }
        return;
    }
  public static void main(String[] args) {
    int[] A={2, 3, -1, -2, 9, 1};
    printPairs(A);
  }
}
Pairs having positive value and negative in the array are: 2 -2 1 -1

복잡성 분석

시간 복잡성

우리는 크기가 n 인 두 개의 중첩 루프를 사용하고 있습니다. 따라서 총 시간 복잡성은 O (N ^ 2)

공간 복잡성

우리는 추가 공간을 사용하지 않으므로 공간 복잡성은 O (1)

접근 방식 2 : 해싱 사용

주요 아이디어

배열에있는 요소를 해시 테이블에 저장할 수 있습니다. 이제 배열의 각 요소 A [i]에 대해 해시 테이블의 –A [i] 값이 1인지 확인하고, 1이면이 쌍을 인쇄하고 A [i] 및 –A 값을 감소시킵니다. [i] 해시 테이블에 1 씩 추가하여 동일한 쌍을 두 번 인쇄하지 않도록합니다.

암호알고리즘

  1. 해시 테이블을 초기화합니다.
  2. 해시 테이블에 각 요소의 빈도를 저장합니다.
  3. 0에서 n-1 사이의 I에 대해 루프 실행
    1. -A [i]가 해시 테이블에 1의 값을 가지고 있으면이 쌍을 인쇄하고 A [i] 및 -A [i]의 값을 1 씩 감소시킵니다.

예를 들어 이해

입력 배열 A [] = {2, 3, -1, -2, 9, 1}을 보겠습니다.

따라서 해시 테이블은 다음과 같습니다.

배열의 양의 음수 값 쌍

이제 배열을 반복하고

주황색은 현재 색인을 보여줍니다.

배열의 양의 음수 값 쌍 배열의 양의 음수 값 쌍

배열의 양의 음수 값 쌍

따라서 최종 출력은 다음과 같습니다. -2 2 -1 1

배열에서 양의 음수 값 쌍을 찾기위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
void printPairs(vector<int> &A)
{
    int n = A.size();
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    cout << "Pairs having positive value and negative in the array are: ";
    for (int i = 0; i < n; i++)
    {
        if (hash_table[-A[i]] == 1)
        {
            if (A[i] <= 0)
            {
                cout << A[i] << " " << (-A[i]) << " ";
            }
            else
            {
                cout << (-A[i]) << " " << A[i] << " ";
            }
            hash_table[A[i]]--;
            hash_table[-A[i]]--;
        }
    }
    cout << endl;
    return;
}
int main()
{
    vector<int> A = {2, 3, -1, -2, 9, 1};
    printPairs(A);
    return 0;
}
Pairs having positive value and negative in the array are: -2 2 -1 1

배열에서 양의 음수 쌍을 찾는 JAVA 프로그램

import java.util.*; 
public class Main
{
    static void printPairs(int[] A)
    {
        int n = A.length;
        HashMap<Integer,Integer> hash_table = new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++)
        {
            hash_table.put(A[i],1);
        }
        System.out.print("Pairs having positive value and negative in the array are: ");
        for (int i = 0; i < n; i++)
        {
            if(hash_table.containsKey(-1*A[i]) && hash_table.get(-1*A[i])==1)
            {
                if (A[i] <= 0)
                {
                    A[i]*=-1;
                }
                System.out.print(A[i]+" -"+A[i]+" ");
                hash_table.put(A[i],0);
                hash_table.put(-1*A[i],0);
            }
        }
        return;
    }
  public static void main(String[] args) {
    int[] A={2, 3, -1, -2, 9, 1};
    printPairs(A);
  }
}
Pairs having positive value and negative in the array are: -2 2 -1 1

복잡성 분석

시간 복잡성

전체 배열을 두 번 반복하므로 시간 복잡성은 의 위에).

공간 복잡성

해시 테이블을 사용하고 있으므로 공간 복잡성은 의 위에).

참조

Translate »