Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ค้นหาจำนวนคู่ (x, y) ในอาร์เรย์ที่ x^y> y^x ใน C ++


สมมติว่าเรามีสองอาร์เรย์ X และ Y ของจำนวนเต็มบวก ค้นหาจำนวนคู่ที่ x^y> y^x โดยที่ x เป็นองค์ประกอบของ X และ y เป็นองค์ประกอบของ Y สมมติว่า X =[2, 1, 6] และ Y =[1, 5] จากนั้นเอาต์พุตจะเป็น 3 เนื่องจากมีสามคู่ เหล่านี้คือ (2, 1), (2, 5) และ (6, 1)

เราสามารถแก้ปัญหานี้ได้อย่างมีประสิทธิภาพ ตรรกะง่ายๆ ก็คือเมื่อ y> x ตามด้วย x^y> y^x โดยมีข้อยกเว้นบางประการ นี่คือเคล็ดลับ

  • จัดเรียงอาร์เรย์ Y

  • สำหรับแต่ละองค์ประกอบ x ใน X เราต้องหาดัชนีของจำนวนที่น้อยที่สุดที่มากกว่า x ใน Y เราจะใช้การค้นหาแบบไบนารีในการทำเช่นนั้น มิฉะนั้น เราก็สามารถใช้ฟังก์ชัน upper_bound() ได้เช่นกัน

  • ตัวเลขทั้งหมดที่อยู่หลังดัชนีที่พบนั้นเป็นไปตามความสัมพันธ์ ดังนั้นให้บวกมันเข้าไปในการนับ

ตัวอย่าง

#include <iostream>
#include <algorithm>
using namespace std;
int count(int x, int Y[], int n, int no_of_y[]) {
   if (x == 0)
      return 0;  
   if (x == 1)
   return no_of_y[0];
   int* index = upper_bound(Y, Y + n, x);
   int ans = (Y + n) - index;
   ans += (no_of_y[0] + no_of_y[1]);
   if (x == 2)
      ans -= (no_of_y[3] + no_of_y[4]);
   if (x == 3)
      ans += no_of_y[2];
   return ans;
}
int howManyPairs(int X[], int Y[], int m, int n) {
   int no_of_y[5] = {0};
   for (int i = 0; i < n; i++)
      if (Y[i] < 5)
         no_of_y[Y[i]]++;
   sort(Y, Y + n);
   int total_pairs = 0;
   for (int i=0; i< m; i++)
      total_pairs += count(X[i], Y, n, no_of_y);
   return total_pairs;
}
int main() {
   int X[] = {2, 1, 6};
   int Y[] = {1, 5};
   int m = sizeof(X)/sizeof(X[0]);
   int n = sizeof(Y)/sizeof(Y[0]);
   cout << "Total pair count: " << howManyPairs(X, Y, m, n);
}

ผลลัพธ์

Total pair count: 3