算法设计（在数组中找到对数(x, y)，使得x^y大于y^x） _数组

本文概述

Python3
C ++
C ++
Java
Python3
C#

给定两个正整数数组X []和Y [], 找到对数, 使得x ^ y > y ^ x其中x是X []的元素, y是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 []的每个元素, 并检查给定条件是否满足。
以下是基于蛮力解决方案的C ++代码。
Python3

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 ++

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)其中中号和?是给定数组的大小。
高效的解决方案：
这个问题可以解决
O(nLogn + mLogn)
时间。诀窍是, 如果
y> x
然后
x ^ y> y ^ x
除了一些例外。
以下是基于此技巧的简单步骤。

排序数组Y []。
对于X []中的每个x, 使用以下公式找到Y []中大于x的最小数字的索引idx(也称为x的ceil)二进制搜索或者我们可以使用内置功能upper_bound()在算法库中。
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; }

Java

// Java program to finds number of pairs (x, y) // in an array such that x^y > y^ximport java.util.Arrays; class Test { // 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 static 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 // getting upperbound of x with binary search int idx = Arrays.binarySearch(Y, x); int ans; if (idx < 0 ){ idx = Math.abs(idx+ 1 ); ans = Y.length - idx; } else { while (idx< n & & Y[idx]==x) { idx++; } ans = Y.length - 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 returns count of pairs (x, y) such that // x belongs to X[], y belongs to Y[] and x^y > y^x static 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[] = new int [ 5 ]; 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 Arrays.sort(Y); 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 method public static void main(String args[]) { int X[] = { 2 , 1 , 6 }; int Y[] = { 1 , 5 }; System.out.println( "Total pairs = " + countPairs(X, Y, X.length, Y.length)); } }

Python3

# Python3 program to find the number # of pairs (x, y) in an array # such that x^y > y^x import bisect# 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 def count(x, Y, n, 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 pairs # 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, bisect.bisect_right # gets address of first greater element # in Y[0..n-1] idx = bisect.bisect_right(Y, x) ans = 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 def count_pairs(X, Y, m, n):# To store counts of 0, 1, 2, 3, # and 4 in array Y NoOfY = [ 0 ] * 5 for i in range (n): if Y[i] < 5 : NoOfY[Y[i]] + = 1# Sort Y so that we can do binary search in it Y.sort() total_pairs = 0 # Initialize result# Take every element of X and # count pairs with it for x in X: total_pairs + = count(x, Y, n, NoOfY)return total_pairs# Driver Code if __name__ = = '__main__' :X = [ 2 , 1 , 6 ] Y = [ 1 , 5 ] print ( "Total pairs = " , count_pairs(X, Y, len (X), len (Y)))# This code is contributed by shaswatd673

// C# program to finds number of pairs (x, y) // in an array such that x^y > y^x using System; class GFG {// 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 static 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 getting // upperbound of x with binary search int idx = Array.BinarySearch(Y, x); int ans; if (idx < 0) { idx = Math.Abs(idx + 1); ans = Y.Length - idx; }else { while (idx< n & & Y[idx] == x) { idx++; } ans = Y.Length - 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 that returns count // of pairs (x, y) such that x belongs // to X[], y belongs to Y[] and x^y > y^x static 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 = new int [5]; 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 Array.Sort(Y); 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 method public static void Main() { int [] X = { 2, 1, 6 }; int [] Y = { 1, 5 }; Console.Write( "Total pairs = " + countPairs(X, Y, X.Length, Y.Length)); } }// This code is contributed by Sam007

输出如下：

Total pairs = 3

时间复杂度：O(nLogn + mLogn), 其中m和n分别是数组X []和Y []的大小。排序步骤需要O(nLogn)时间。然后, 使用二进制搜索在Y []中搜索X []的每个元素。此步骤需要O(mLogn)时间。
【算法设计（在数组中找到对数(x, y)，使得x^y大于y^x）】本文作者：Shubham Mittal。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。