Cari pasangan nilai positif dan negatif dalam tatasusunan menggunakan C++

Dalam artikel ini, kami mempunyai tatasusunan dengan elemen yang berbeza. Kita perlu mencetak pasangan nilai positif dan negatif dalam tatasusunan dengan nilai mutlak yang sama dan mencetaknya dalam susunan disusun seperti-

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

Kaedah untuk mencari penyelesaian

Kaedah pertama yang kami fikirkan ialah kaedah brute force dan kemudian kami juga menghasilkan satu kaedah yang dipanggil kaedah kecekapan tinggi. Kami akan membincangkan kedua-dua kaedah.

Kaedah Brute Force

Dalam kaedah ini kita akan mengulangi tatasusunan dengan satu indeks dan mencari nilai mutlak yang sama tetapi indeks yang berbeza. Contoh

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

Sekarang kita menggunakan dua untuk gelung, dan kerumitan masa keseluruhan ialah O(N*N). N ialah saiz tatasusunan yang diberikan, berfungsi dengan baik untuk kekangan yang lebih rendah, tetapi tidak baik untuk kekangan yang lebih tinggi, jadi sekarang kita akan membincangkan pendekatan lain.

Kaedah yang cekap

Dalam kaedah ini, kami akan menggunakan peta cincang, yang akan mengurangkan kerumitan masa kami.

Contoh

-1 1 -12 12 -56 56

Output

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

Penjelasan kod di atas

Dalam pendekatan ini, kami menggunakan peta cincang untuk menyimpan kekerapan nombor semasa kami mengulangi tatasusunan, kami kini mengemas kini kekerapan nilai mutlak daripada elemen semasa, Memandangkan anda tahu bahawa semua pasangan mempunyai nilai 2, kami sedang melintasi peta.

Jika kekerapan sebarang nombor ialah 2, maka kami menyimpannya dalam nombor dan akhirnya, kami mencetak nilai dalam susunan yang disusun. (Memandangkan peta mengandungi nombor dalam susunan yang diisih, kami tidak perlu mengisih vektor berangka).

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah mencari pasangan nilai positif dan negatif dalam tatasusunan menggunakan teknik pencincangan. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan cara lengkap untuk menyelesaikan masalah ini (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Kami berharap artikel ini dapat membantu anda.

Atas ialah kandungan terperinci Cari pasangan nilai positif dan negatif dalam tatasusunan menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!