# 查找數組中的對數（x，y），使得 x ^ y > y ^ x > 原文： [https://www.geeksforgeeks.org/find-number-pairs-xy-yx/](https://www.geeksforgeeks.org/find-number-pairs-xy-yx/) 給定正整數的兩個數組 X []和 Y []，找到對數，使得 **x ^ y > y ^ x** 其中 x 是 X []的元素，而 y 是 X []的元素 Y []。 例子： > **輸入**： X [] = {2，1，6}，Y = {1，5} > **輸出**： 3 > **說明**： 共 3 對，其中 pow（x，y）比 pow（y，x）大 > 對是（2，1），（2，5）和（6，1） > > **輸入**： X [] = {10，19，18}，Y [] = {11，15，9} > **輸出**： 2 > **說明 **：總共有 2 對，其中 pow（x，y）比 pow（y，x）大 > 對是（10，11）和（10，15） **暴力解**將考慮 X []和 Y []的每個元素，并檢查給定條件是否滿足。 Following is C++ code based on brute force solution. ## Python3 ```py def countPairsBruteForce(X, Y, m, n): ????ans = 0? ????for i in range(m): ????????for j in range(n): ????????????if (pow(X[i], Y[j]) > pow(Y[j], X[i])): ????????????????ans+=1? ????return ans? # This code is contributed by shubhamsingh10 ``` ## C++ ```cpp int countPairsBruteForce(int X[], int Y[], int m, int n) { ????int ans = 0; ????for (int i = 0; i < m; i++) ???????for (int j = 0; j < n; j++) ??????????if (pow(X[i], Y[j]) > pow(Y[j], X[i])) ??????????????ans++; ????return ans; } ``` **時間復雜度**：O（M * N），其中 **M** 和 **N** 是給定數組的大小。 **有效解決方案**： 該問題可以在 **O（nLogn + mLogn）**時間內解決。 這里的竅門是，如果 **y > x** ，則 **x ^ y > y ^ x** 除外。 以下是基于此技巧的簡單步驟。 * 對數組 Y []進行排序。 * 對于[[X]]中的每個 x，請使用**二分搜索**查找 Y []中大于 x 的最小數字的索引 idx（也稱為 x 的 ceil），或者我們可以使用內置函數 [upper_bound（ ）](http://www.geeksforgeeks.org/stdupper_bound-in-cpp/)在算法庫中。 * idx 之后的所有數字都滿足關系，因此只需將（n-idx）添加到計數中即可。 **基本情況和例外**： 以下是 X []中的 x 和 Y []中的 y 的例外。 * 如果 x = 0，則此 x 的對數為 0。 * 如果 x = 1，則此 x 的對數等于 Y []中的 0s 數。 * x 小于 y 表示 x ^ y 大于 y ^ x。 1. x = 2，y = 3 或 4 2. x = 3，y = 2 注意，不存在 x = 4 和 y = 2 的情況 下圖以表格形式顯示了所有例外情況。 值 1 表示對應的（x，y）形成有效對。  在以下實現中，我們對 Y 數組進行預處理，并對其中的 0、1、2、3 和 4 進行計數，以便我們可以在恒定時間內處理所有異常。 數組 NoOfY []用于存儲計數。 下面是上述方法的實現： ## C++ ``` // C++ program to finds the number of pairs (x, y) // in an array such that x^y > y^x #include<bits/stdc++.h> using namespace std; // Function to return count of pairs with x as one element // of the pair. It mainly looks for all values in Y[] where // x ^ Y[i] > Y[i] ^ x int count(int x, int Y[], int n, int NoOfY[]) { ????// If x is 0, then there cannot be any value in Y such that ????// x^Y[i] > Y[i]^x ????if (x == 0) return 0; ????// If x is 1, then the number of pais is equal to number of ????// zeroes in Y[] ????if (x == 1) return NoOfY[0]; ????// Find number of elements in Y[] with values greater than x ????// upper_bound() gets address of first greater element in Y[0..n-1] ????int* idx = upper_bound(Y, Y + n, x); ????int ans = (Y + n) - idx; ????// If we have reached here, then x must be greater than 1, ????// increase number of pairs for y=0 and y=1 ????ans += (NoOfY[0] + NoOfY[1]); ????// Decrease number of pairs for x=2 and (y=4 or y=3) ????if (x == 2)? ans -= (NoOfY[3] + NoOfY[4]); ????// Increase number of pairs for x=3 and y=2 ????if (x == 3)? ans += NoOfY[2]; ????return ans; } // Function to return count of pairs (x, y) such that // x belongs to X[], y belongs to Y[] and x^y > y^x int countPairs(int X[], int Y[], int m, int n) { ????// To store counts of 0, 1, 2, 3 and 4 in array Y ????int NoOfY[5] = {0}; ????for (int i = 0; i < n; i++) ????????if (Y[i] < 5) ????????????NoOfY[Y[i]]++; ????// Sort Y[] so that we can do binary search in it ????sort(Y, Y + n); ????int total_pairs = 0; // Initialize result ????// Take every element of X and count pairs with it ????for (int i=0; i<m; i++) ????????total_pairs += count(X[i], Y, n, NoOfY); ????return total_pairs; } // Driver program? 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 pairs = " << countPairs(X, Y, m, n); ????return 0; } ```