给出一个由n个整数和一个整数K组成的数组。求出无序对的总数{i，j}，使（ai+aj–K）的绝对值，即| ai+aj–K |在i！=J 例如：
null
Input : arr[] = {0, 4, 6, 2, 4}, K = 7Output : Minimal Value = 1 Total Pairs = 5 Explanation : Pairs resulting minimal value are : {a1, a3}, {a2, a4}, {a2, a5}, {a3, a4}, {a4, a5} Input : arr[] = {4, 6, 2, 4} , K = 9Output : Minimal Value = 1 Total Pairs = 4 Explanation : Pairs resulting minimal value are : {a1, a2}, {a1, a4}, {a2, a3}, {a2, a4}
A. 简单解决方案 迭代所有可能的对，对于每一对，我们将检查（ai+aj–K）的值是否小于当前的最小值not。根据上述情况的结果，我们总共有三个病例：
- abs（ai+aj–K）>最小 ：不执行任何操作，因为这对将不计入最小可能值。
- abs（ai+aj–K）=最小 ：增加对的计数，得到最小可能值。
- abs（ai+aj–K） ：更新最小值并将计数设置为1。
C++
// CPP program to find number of pairs and minimal // possible value #include<bits/stdc++.h> using namespace std; // function for finding pairs and min value void pairs( int arr[], int n, int k) { // initialize smallest and count int smallest = INT_MAX; int count=0; // iterate over all pairs for ( int i=0; i<n; i++) for ( int j=i+1; j<n; j++) { // is abs value is smaller than smallest // update smallest and reset count to 1 if ( abs (arr[i] + arr[j] - k) < smallest ) { smallest = abs (arr[i] + arr[j] - k); count = 1; } // if abs value is equal to smallest // increment count value else if ( abs (arr[i] + arr[j] - k) == smallest) count++; } // print result cout << "Minimal Value = " << smallest << "" ; cout << "Total Pairs = " << count << "" ; } // driver program int main() { int arr[] = {3, 5, 7, 5, 1, 9, 9}; int k = 12; int n = sizeof (arr) / sizeof (arr[0]); pairs(arr, n, k); return 0; } |
JAVA
// Java program to find number of pairs // and minimal possible value import java.util.*; class GFG { // function for finding pairs and min value static void pairs( int arr[], int n, int k) { // initialize smallest and count int smallest = Integer.MAX_VALUE; int count= 0 ; // iterate over all pairs for ( int i= 0 ; i<n; i++) for ( int j=i+ 1 ; j<n; j++) { // is abs value is smaller than // smallest update smallest and // reset count to 1 if ( Math.abs(arr[i] + arr[j] - k) < smallest ) { smallest = Math.abs(arr[i] + arr[j] - k); count = 1 ; } // if abs value is equal to smallest // increment count value else if (Math.abs(arr[i] + arr[j] - k) == smallest) count++; } // print result System.out.println( "Minimal Value = " + smallest); System.out.println( "Total Pairs = " + count); } /* Driver program to test above function */ public static void main(String[] args) { int arr[] = { 3 , 5 , 7 , 5 , 1 , 9 , 9 }; int k = 12 ; int n = arr.length; pairs(arr, n, k); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 program to find number of pairs # and minimal possible value # function for finding pairs and min value def pairs(arr, n, k): # initialize smallest and count smallest = 999999999999 count = 0 # iterate over all pairs for i in range (n): for j in range (i + 1 , n): # is abs value is smaller than smallest # update smallest and reset count to 1 if abs (arr[i] + arr[j] - k) < smallest: smallest = abs (arr[i] + arr[j] - k) count = 1 # if abs value is equal to smallest # increment count value elif abs (arr[i] + arr[j] - k) = = smallest: count + = 1 # print result print ( "Minimal Value = " , smallest) print ( "Total Pairs = " , count) # Driver Code if __name__ = = '__main__' : arr = [ 3 , 5 , 7 , 5 , 1 , 9 , 9 ] k = 12 n = len (arr) pairs(arr, n, k) # This code is contributed by PranchalK |
C#
// C# program to find number // of pairs and minimal // possible value using System; class GFG { // function for finding // pairs and min value static void pairs( int []arr, int n, int k) { // initialize // smallest and count int smallest = 0; int count = 0; // iterate over all pairs for ( int i = 0; i < n; i++) for ( int j = i + 1; j < n; j++) { // is abs value is smaller // than smallest update // smallest and reset // count to 1 if (Math.Abs(arr[i] + arr[j] - k) < smallest ) { smallest = Math.Abs(arr[i] + arr[j] - k); count = 1; } // if abs value is equal // to smallest increment // count value else if (Math.Abs(arr[i] + arr[j] - k) == smallest) count++; } // print result Console.WriteLine( "Minimal Value = " + smallest); Console.WriteLine( "Total Pairs = " + count); } // Driver Code public static void Main() { int []arr = {3, 5, 7, 5, 1, 9, 9}; int k = 12; int n = arr.Length; pairs(arr, n, k); } } // This code is contributed // by anuj_67. |
PHP
<?php // PHP program to find number of // pairs and minimal possible value // function for finding pairs // and min value function pairs( $arr , $n , $k ) { // initialize smallest and count $smallest = PHP_INT_MAX; $count = 0; // iterate over all pairs for ( $i = 0; $i < $n ; $i ++) for ( $j = $i + 1; $j < $n ; $j ++) { // is abs value is smaller than smallest // update smallest and reset count to 1 if ( abs ( $arr [ $i ] + $arr [ $j ] - $k ) < $smallest ) { $smallest = abs ( $arr [ $i ] + $arr [ $j ] - $k ); $count = 1; } // if abs value is equal to smallest // increment count value else if ( abs ( $arr [ $i ] + $arr [ $j ] - $k ) == $smallest ) $count ++; } // print result echo "Minimal Value = " , $smallest , "" ; echo "Total Pairs = " , $count , "" ; } // Driver Code $arr = array (3, 5, 7, 5, 1, 9, 9); $k = 12; $n = sizeof( $arr ); pairs( $arr , $n , $k ); // This code is contributed by aj_36 ?> |
Javascript
<script> // Javascript program to find number of pairs and minimal // possible value // function for finding pairs and min value function pairs(arr, n, k) { // initialize smallest and count var smallest = 1000000000; var count=0; // iterate over all pairs for ( var i=0; i<n; i++) for ( var j=i+1; j<n; j++) { // is Math.abs value is smaller than smallest // update smallest and reset count to 1 if ( Math.abs(arr[i] + arr[j] - k) < smallest ) { smallest = Math.abs(arr[i] + arr[j] - k); count = 1; } // if Math.abs value is equal to smallest // increment count value else if (Math.abs(arr[i] + arr[j] - k) == smallest) count++; } // print result document.write( "Minimal Value = " + smallest + "<br>" ); document.write( "Total Pairs = " + count + "<br>" ); } // driver program var arr = [3, 5, 7, 5, 1, 9, 9]; var k = 12; var n = arr.length; pairs(arr, n, k); </script> |
输出：
Minimal Value = 0Total Pairs = 4
一 有效解决方案 是使用自平衡二叉搜索树（它是在C++中实现的，在java中是树集）。我们可以在地图上找到O（对数n）时间内最近的元素。
C++
// C++ program to find number of pairs // and minimal possible value #include<bits/stdc++.h> using namespace std; // function for finding pairs and min value void pairs( int arr[], int n, int k) { // initialize smallest and count int smallest = INT_MAX, count = 0; set< int > s; // iterate over all pairs s.insert(arr[0]); for ( int i=1; i<n; i++) { // Find the closest elements to k - arr[i] int lower = *lower_bound(s.begin(), s.end(), k - arr[i]); int upper = *upper_bound(s.begin(), s.end(), k - arr[i]); // Find absolute value of the pairs formed // with closest greater and smaller elements. int curr_min = min( abs (lower + arr[i] - k), abs (upper + arr[i] - k)); // is abs value is smaller than smallest // update smallest and reset count to 1 if (curr_min < smallest) { smallest = curr_min; count = 1; } // if abs value is equal to smallest // increment count value else if (curr_min == smallest ) count++; s.insert(arr[i]); } // print result cout << "Minimal Value = " << smallest << "" ; cout << "Total Pairs = " << count << "" ; } // driver program int main() { int arr[] = {3, 5, 7, 5, 1, 9, 9}; int k = 12; int n = sizeof (arr) / sizeof (arr[0]); pairs(arr, n, k); return 0; } |
JAVA
// Java program to find number of pairs // and minimal possible value import java.util.*; class GFG { // function for finding pairs and min value static void pairs( int arr[], int n, int k) { // initialize smallest and count int smallest = Integer.MAX_VALUE; int count = 0 ; // iterate over all pairs for ( int i = 0 ; i < n; i++) for ( int j = i + 1 ; j < n; j++) { // is abs value is smaller than // smallest update smallest and // reset count to 1 if ( Math.abs(arr[i] + arr[j] - k) < smallest ) { smallest = Math.abs(arr[i] + arr[j] - k); count = 1 ; } // if abs value is equal to smallest // increment count value else if (Math.abs(arr[i] + arr[j] - k) == smallest) count++; } // print result System.out.println( "Minimal Value = " + smallest); System.out.println( "Total Pairs = " + count); } /* Driver program to test above function */ public static void main(String[] args) { int arr[] = { 3 , 5 , 7 , 5 , 1 , 9 , 9 }; int k = 12 ; int n = arr.length; pairs(arr, n, k); } } // This code is contributed by Rajput-Ji |
C#
// C# program to find number of pairs // and minimal possible value using System; public class GFG { // function for finding pairs and min value static void pairs( int []arr, int n, int k) { // initialize smallest and count int smallest = int .MaxValue; int count = 0; // iterate over all pairs for ( int i = 0; i < n; i++) for ( int j = i + 1; j < n; j++) { // is abs value is smaller than // smallest update smallest and // reset count to 1 if (Math.Abs(arr[i] + arr[j] - k) < smallest) { smallest = Math.Abs(arr[i] + arr[j] - k); count = 1; } // if abs value is equal to smallest // increment count value else if (Math.Abs(arr[i] + arr[j] - k) == smallest) count++; } // print result Console.WriteLine( "Minimal Value = " + smallest); Console.WriteLine( "Total Pairs = " + count); } /* Driver program to test above function */ public static void Main(String[] args) { int []arr = { 3, 5, 7, 5, 1, 9, 9 }; int k = 12; int n = arr.Length; pairs(arr, n, k); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // javascript program to find number of pairs // and minimal possible value // function for finding pairs and min value function pairs(arr , n , k) { // initialize smallest and count var smallest = Number.MAX_VALUE; var count = 0; // iterate over all pairs for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) { // is abs value is smaller than // smallest update smallest and // reset count to 1 if (Math.abs(arr[i] + arr[j] - k) < smallest) { smallest = Math.abs(arr[i] + arr[j] - k); count = 1; } // if abs value is equal to smallest // increment count value else if (Math.abs(arr[i] + arr[j] - k) == smallest) count++; } // print result document.write( "Minimal Value = " + smallest); document.write( "<br/>Total Pairs = " + count); } /* Driver program to test above function */ var arr = [ 3, 5, 7, 5, 1, 9, 9 ]; var k = 12; var n = arr.length; pairs(arr, n, k); // This code is contributed by Rajput-Ji </script> |
输出：
Minimal Value = 0Total Pairs = 4
时间复杂性： O（n日志n） 本文由 希瓦姆·普拉丹（anuj_charm） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
