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

해결 방법을 찾는 방법

우리가 처음 생각한 방법은 무차별 대입 방식이었습니다. 그리고 우리는 고효율 방식이라는 A 방식도 고안했습니다. 우리는 두 가지 방법을 모두 논의할 것입니다.

무차별 대입 방법

이 방법에서는 하나의 인덱스를 사용하여 배열을 반복하고 동일한 절대값이지만 다른 인덱스를 찾습니다.

Example

#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 << " ";
}

Output

-1 1 -12 12 -56 56

이 접근 방식에서는 두 개의 루프를 사용하여 배열을 반복하고 다른 요소를 찾으면 코드 속도를 높이기 위해 내부 루프에서 뛰어납니다. 이제 두 개의 for 루프를 사용하고 전체 시간 복잡도는 O(N*N)입니다. N은 주어진 배열의 크기이며 낮은 제약 조건에서는 잘 작동하지만 높은 제약 조건에서는 적합하지 않으므로 이제 다른 접근 방식에 대해 논의하겠습니다.

효율적인 방법

이 방법에서는 해시 맵을 사용하므로 시간 복잡도가 크게 줄어듭니다.

Example

#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 << " ";
}

Output

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

위 코드 설명

이 접근 방식에서는 해시맵을 사용하여 배열을 반복하면서 숫자의 빈도를 저장하고 있으며 이제 절대값의 빈도를 업데이트합니다. 현재 요소의 모든 쌍이 값 2를 갖는다는 것을 알고 있으므로 맵을 순회합니다.

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

결론

이 기사에서는 해싱 기술을 사용하여 배열에서 양수 값과 음수 값 쌍을 찾는 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하는 완전한 방법(정상적이고 효율적인)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

위 내용은 C++를 사용하여 배열에서 양수 값과 음수 값 쌍 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!