给定一个排序整数数组和数字k，任务是对乘积小于x的数组中的对进行计数。 例如：
null
输入： A={2,3,5,6}，k=16 输出： 4. 乘积小于16的对：（2,3）、（2,5）、（2,6）、（3,5） 输入： A={2,3,4,6,9}，k=20 输出： 6. 乘积小于20的对：（2,3）、（2,4）、（2,6）、（2,9）、（3,4）、（3,6）
A. 简单解决方案 对于这个问题，运行两个循环来生成所有对，并逐个生成，检查当前对的乘积是否小于x。 一 有效解决方案 这个问题的关键是取l和r变量中索引的初始值和最后一个值。考虑以下两种情况：
- 案例一： 让我们考虑i
类似地，A[i]*A[j-2] - 案例二： 让我们考虑i k，然后我们可以说，对于排序数组，[i] *[j+1]＞k为[j+2]＞a[j]， 类似地，A[i]*A[j+2]>k，A[i]*A[j+3]>k…。。，A[i]*A[n-1]>k。
上述问题类似于 在排序数组中计数总和小于x的对 ，唯一不同的是求对的乘积，而不是求和。 下面是解决这个问题的算法：
1) Initialize two variables l and r to find the candidate elements in the sorted array. (a) l = 0 (b) r = n - 12) Initialize : result = 02) Loop while l < r. // If current left and current // right have product smaller than x, // the all elements from l+1 to r // form a pair with current (a) If (arr[l] * arr[r] < x) result = result + (r - l) l++; (b) Else r--; 3) Return result
下面是上述算法的实现：
C++
// C++ program to find number of pairs with // product less than k in a sorted array #include <bits/stdc++.h> using namespace std; // Function to count the pairs int fun( int A[], int n, int k) { // count to keep count of // number of pairs with product // less than k int count = 0; int i = 0; int j = n - 1; // Traverse the array while (i < j) { // If product is less than k // then count that pair // and increment 'i' if (A[i] * A[j] < k) { count += (j - i); i++; } // Else decrement 'j' else { j--; } } // Return count of pairs return count; } // Driver code int main() { int A[] = { 2, 3, 4, 6, 9 }; int n = sizeof (A) / sizeof ( int ); int k = 20; cout << "Number of pairs with product less than " << k << " = " << fun(A, n, k) << endl; return 0; } |
JAVA
// Java program to find number // of pairs with product less // than k in a sorted array class GFG { // Function to count the pairs static int fun( int A[], int n, int k) { // count to keep count of // number of pairs with // product less than k int count = 0 ; int i = 0 ; int j = n - 1 ; // Traverse the array while (i < j) { // If product is less than // k then count that pair // and increment 'i' if (A[i] * A[j] < k) { count += (j - i); i++; } // Else decrement 'j' else { j--; } } // Return count of pairs return count; } // Driver code public static void main(String args[]) { int A[] = { 2 , 3 , 4 , 6 , 9 }; int n = A.length; int k = 20 ; System.out.println( "Number of pairs with " + "product less than 20 = " + fun(A, n, k)); } } // This code is contributed // by Kirti_Mangal |
python
# Python program to find number of pairs with # product less than k in a sorted array def fun(A, k): # count to keep count of number # of pairs with product less than k count = 0 n = len (A) # Left pointer pointing to leftmost part i = 0 # Right pointer pointing to rightmost part j = n - 1 # While left and right pointer don't meet while i < j: if A[i] * A[j] < k: count + = (j - i) # Increment the left pointer i + = 1 else : # Decrement the right pointer j - = 1 return count # Driver code to test above function A = [ 2 , 3 , 4 , 6 , 9 ] k = 20 print ( "Number of pairs with product less than " , k, " = " , fun(A, k)) |
C#
// C# program to find number // of pairs with product less // than k in a sorted array using System; class GFG { // Function to count the pairs static int fun( int []A, int n, int k) { // count to keep count of // number of pairs with // product less than k int count = 0; int i = 0; int j = n - 1; // Traverse the array while (i < j) { // If product is less than // k then count that pair // and increment 'i' if (A[i] * A[j] < k) { count += (j - i); i++; } // Else decrement 'j' else { j--; } } // Return count of pairs return count; } // Driver code public static void Main() { int []A = {2, 3, 4, 6, 9}; int n = A.Length; int k = 20; Console.WriteLine( "Number of pairs with " + "product less than 20 = " + fun(A, n, k)); } } // This code is contributed // by Subhadeep |
PHP
<?php // PHP program to find number of // pairs with product less than k // in a sorted array // Function to count the pairs function fun( $A , $n , $k ) { // count to keep count of // number of pairs with product // less than k $count = 0; $i = 0; $j = ( $n - 1); // Traverse the array while ( $i < $j ) { // If product is less than k // then count that pair // and increment 'i' if ( $A [ $i ] * $A [ $j ] < $k ) { $count += ( $j - $i ); $i ++; } // Else decrement 'j' else { $j --; } } // Return count of pairs return $count ; } // Driver code $A = array ( 2, 3, 4, 6, 9 ); $n = sizeof( $A ); $k = 20; echo "Number of pairs with product less than " , $k , " = " , fun( $A , $n , $k ) , "" ; // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to find number // of pairs with product less // than k in a sorted array // Function to count the pairs function fun(A, n, k) { // count to keep count of // number of pairs with // product less than k let count = 0; let i = 0; let j = n - 1; // Traverse the array while (i < j) { // If product is less than // k then count that pair // and increment 'i' if (A[i] * A[j] < k) { count += (j - i); i++; } // Else decrement 'j' else { j--; } } // Return count of pairs return count; } let A = [2, 3, 4, 6, 9]; let n = A.length; let k = 20; document.write( "Number of pairs with " + "product less than 20 = " + fun(A, n, k)); </script> |
输出：
Number of pairs with product less than 20 = 6
时间复杂性： O（N）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
