한 쌍의 양수 음수 값 정렬 문제 우리는 고유 한 정수의 배열 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]가 있는지 확인한 다음이 쌍을 인쇄합니다.
암호알고리즘
- 0에서 n-1 사이의 I에 대해 루프 실행
- i + 1 ~ n-1 범위에서 j에 대해 루프 실행
- A [i]가 -A [j]와 같으면이 쌍을 인쇄합니다.
- 반환.
- i + 1 ~ n-1 범위에서 j에 대해 루프 실행
배열에서 양의 음수 값 쌍을 찾기위한 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 씩 추가하여 동일한 쌍을 두 번 인쇄하지 않도록합니다.
암호알고리즘
- 해시 테이블을 초기화합니다.
- 해시 테이블에 각 요소의 빈도를 저장합니다.
- 0에서 n-1 사이의 I에 대해 루프 실행
- -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
복잡성 분석
시간 복잡성
전체 배열을 두 번 반복하므로 시간 복잡성은 의 위에).
공간 복잡성
해시 테이블을 사용하고 있으므로 공간 복잡성은 의 위에).
