C++를 사용하여 배열에서 양수 값 쌍 찾기

이 기사에는 고유한 요소를 포함하는 배열이 있습니다. 동일한 절대값을 가진 배열의 양수 값 쌍을 인쇄하고 예를 들어 정렬된 순서로 인쇄해야 합니다. -

Input : arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88}
Output : -1 1 -12 12 -56 56

Input : arr[] = {30, 40, 50, 77, -51, -50, -40}
Output : -40 40 -50 50

해결책을 찾기 위한 접근 방식

가장 먼저 떠오르는 접근 방식은 Brute Force 접근 방식이며 우리는 Efficient 접근 방식이라는 또 다른 접근 방식을 구성합니다. 우리는 두 가지 접근 방식에 대해 논의할 것입니다.

무차별 대입 접근

이 접근 방식에서 우리는 하나의 인덱스를 가지고 배열을 탐색하고 절대값은 같지만 인덱스는 다른 것을 찾습니다.

예시

#include<bits/stdc++.h>
using namespace std;

int main() {
   int arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88 };
   int n = sizeof(arr)/sizeof(int); // size of our array.
   vector<int> nums; // the present pairs.

   for(int i = 0; i < n; i++) {
      for(int j = i+1; j < n; j++) {
         if(abs(arr[j]) == abs(arr[i])) { // finding the pairs.
            nums.push_back(abs(arr[i]));
            break;
            // if we found the pair then we can just break as there are distinct elements in the array.
         }
      }
   }
   sort(nums.begin(), nums.end());
   for(auto x : nums) // printing the pairs.
      cout << -x << " " << x << " ";
}

출력

-1 1 -12 12 -56 56

이 접근 방식에서는 배열을 탐색하고 다른 요소를 찾기 위해 두 개의 루프를 사용합니다. 다른 요소를 찾으면 내부 루프에서 벗어나 코드를 더 빠르게 실행합니다. 이제 두 개의 for 루프를 사용하므로 전체 시간 복잡도는 O(N*N)입니다. N은 낮은 제약 조건에는 적합하지만 높은 제약 조건에는 좋지 않은 주어진 배열의 크기이므로 이제 다른 접근 방식에 대해 논의하겠습니다.

효율적인 접근

이 접근 방식에서는 시간 복잡성을 크게 줄이는 데 도움이 되는 해시맵을 사용합니다.

예시

#include<bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };
   int n = sizeof(arr)/sizeof(int); // size of our array.
   map<int, int> found; // going to store the count of numbers found.
   vector<int> nums; // the present pairs.
   for(int i = 0; i < n; i++)
      found[abs(arr[i])]++; // increasing the frequency of abs(arr[i]).
   for(auto x : found) { // traversing the map.
      if(x.second == 2) // if any numbers frequency is two then push it to nums.
         nums.push_back(x.first);
   }
   for(auto x : nums) // printing the pairs.
      cout << -x << " " << x << " ";
}

출력

-1 1 -4 4 -8 8 -9 9

위 코드 설명

이 접근 방식에서는 해시맵을 사용하여 숫자의 빈도를 저장합니다. 배열을 탐색할 때 모든 쌍의 값이 2라는 것을 알고 있으므로 현재 요소의 절대값 빈도를 업데이트하고 있으므로 지도를 탐색합니다.

임의의 숫자의 빈도가 2이면 숫자로 저장하고 마지막으로 값을 정렬된 순서로 인쇄합니다. (지도에는 숫자가 정렬된 순서로 포함되어 있으므로 숫자 벡터를 정렬할 필요가 없습니다.)

결론

이 기사에서는 해싱 기법을 사용하여 배열에서 양의 음수 값 쌍을 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식( Normal 및 Efficient)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.