问题: 给出了一个整数数组，包括+ve和-ve。你需要找到这两个元素，使它们的和最接近于零。 对于下面的数组，程序应该打印-80和85。
null
方法1（简单） 对于每个元素，找到它与数组中每个其他元素的和，并比较和。最后，返回最小和。
实施 :
C++
// C++ code to find Two elements // whose sum is closest to zero # include <bits/stdc++.h> # include <stdlib.h> /* for abs() */ # include <math.h> using namespace std; void minAbsSumPair( int arr[], int arr_size) { int inv_count = 0; int l, r, min_sum, sum, min_l, min_r; /* Array should have at least two elements*/ if (arr_size < 2) { cout << "Invalid Input" ; return ; } /* Initialization of values */ min_l = 0; min_r = 1; min_sum = arr[0] + arr[1]; for (l = 0; l < arr_size - 1; l++) { for (r = l + 1; r < arr_size; r++) { sum = arr[l] + arr[r]; if ( abs (min_sum) > abs (sum)) { min_sum = sum; min_l = l; min_r = r; } } } cout << "The two elements whose sum is minimum are " << arr[min_l] << " and " << arr[min_r]; } // Driver Code int main() { int arr[] = {1, 60, -10, 70, -80, 85}; minAbsSumPair(arr, 6); return 0; } // This code is contributed // by Akanksha Rai(Abby_akku) |
C
// C code to find Two elements // whose sum is closest to zero # include <stdio.h> # include <stdlib.h> /* for abs() */ # include <math.h> void minAbsSumPair( int arr[], int arr_size) { int inv_count = 0; int l, r, min_sum, sum, min_l, min_r; /* Array should have at least two elements*/ if (arr_size < 2) { printf ( "Invalid Input" ); return ; } /* Initialization of values */ min_l = 0; min_r = 1; min_sum = arr[0] + arr[1]; for (l = 0; l < arr_size - 1; l++) { for (r = l+1; r < arr_size; r++) { sum = arr[l] + arr[r]; if ( abs (min_sum) > abs (sum)) { min_sum = sum; min_l = l; min_r = r; } } } printf ( " The two elements whose sum is minimum are %d and %d" , arr[min_l], arr[min_r]); } /* Driver program to test above function */ int main() { int arr[] = {1, 60, -10, 70, -80, 85}; minAbsSumPair(arr, 6); getchar (); return 0; } |
JAVA
// Java code to find Two elements // whose sum is closest to zero import java.util.*; import java.lang.*; class Main { static void minAbsSumPair( int arr[], int arr_size) { int inv_count = 0 ; int l, r, min_sum, sum, min_l, min_r; /* Array should have at least two elements*/ if (arr_size < 2 ) { System.out.println( "Invalid Input" ); return ; } /* Initialization of values */ min_l = 0 ; min_r = 1 ; min_sum = arr[ 0 ] + arr[ 1 ]; for (l = 0 ; l < arr_size - 1 ; l++) { for (r = l+ 1 ; r < arr_size; r++) { sum = arr[l] + arr[r]; if (Math.abs(min_sum) > Math.abs(sum)) { min_sum = sum; min_l = l; min_r = r; } } } System.out.println( " The two elements whose " + "sum is minimum are " + arr[min_l]+ " and " +arr[min_r]); } // main function public static void main (String[] args) { int arr[] = { 1 , 60 , - 10 , 70 , - 80 , 85 }; minAbsSumPair(arr, 6 ); } } |
蟒蛇3
# Python3 code to find Two elements # whose sum is closest to zero def minAbsSumPair(arr,arr_size): inv_count = 0 # Array should have at least # two elements if arr_size < 2 : print ( "Invalid Input" ) return # Initialization of values min_l = 0 min_r = 1 min_sum = arr[ 0 ] + arr[ 1 ] for l in range ( 0 , arr_size - 1 ): for r in range (l + 1 , arr_size): sum = arr[l] + arr[r] if abs (min_sum) > abs ( sum ): min_sum = sum min_l = l min_r = r print ( "The two elements whose sum is minimum are" , arr[min_l], "and " , arr[min_r]) # Driver program to test above function arr = [ 1 , 60 , - 10 , 70 , - 80 , 85 ] minAbsSumPair(arr, 6 ); # This code is contributed by Smitha Dinesh Semwal |
C#
// C# code to find Two elements // whose sum is closest to zero using System; class GFG { static void minAbsSumPair( int []arr, int arr_size) { int l, r, min_sum, sum, min_l, min_r; /* Array should have at least two elements*/ if (arr_size < 2) { Console.Write( "Invalid Input" ); return ; } /* Initialization of values */ min_l = 0; min_r = 1; min_sum = arr[0] + arr[1]; for (l = 0; l < arr_size - 1; l++) { for (r = l+1; r < arr_size; r++) { sum = arr[l] + arr[r]; if (Math.Abs(min_sum) > Math.Abs(sum)) { min_sum = sum; min_l = l; min_r = r; } } } Console.Write( " The two elements whose " + "sum is minimum are " + arr[min_l]+ " and " +arr[min_r]); } // main function public static void Main () { int []arr = {1, 60, -10, 70, -80, 85}; minAbsSumPair(arr, 6); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to find the Two elements // whose sum is closest to zero function minAbsSumPair( $arr , $arr_size ) { $inv_count = 0; /* Array should have at least two elements*/ if ( $arr_size < 2) { echo "Invalid Input" ; return ; } /* Initialization of values */ $min_l = 0; $min_r = 1; $min_sum = $arr [0] + $arr [1]; for ( $l = 0; $l < $arr_size - 1; $l ++) { for ( $r = $l +1; $r < $arr_size ; $r ++) { $sum = $arr [ $l ] + $arr [ $r ]; if ( abs ( $min_sum ) > abs ( $sum )) { $min_sum = $sum ; $min_l = $l ; $min_r = $r ; } } } echo "The two elements whose sum is minimum are " . $arr [ $min_l ]. " and " . $arr [ $min_r ]; } // Driver Code $arr = array (1, 60, -10, 70, -80, 85); minAbsSumPair( $arr , 6); // This code is contributed by Sam007 ?> |
Javascript
<script> // JavaScript code to find Two elements // whose sum is closest to zero function minAbsSumPair( arr, arr_size) { var inv_count = 0; var l, r, min_sum, sum, min_l, min_r; /* Array should have at least two elements*/ if (arr_size < 2) { document.write( "Invalid Input" ); return ; } /* Initialization of values */ min_l = 0; min_r = 1; min_sum = arr[0] + arr[1]; for (l = 0; l < arr_size - 1; l++) { for (r = l + 1; r < arr_size; r++) { sum = arr[l] + arr[r]; if (Math.abs(min_sum) > Math.abs(sum)) { min_sum = sum; min_l = l; min_r = r; } } } document.write( "The two elements whose sum is minimum are " + arr[min_l] + " and " + arr[min_r]); } // Driver Code arr = new Array(1, 60, -10, 70, -80, 85); minAbsSumPair(arr, 6); // This code is contributed by simranarora5sos </script> |
输出：
The two elements whose sum is minimum are -80 and 85
时间复杂性： O（n^2）
方法2（使用排序）：
算法 1） 对输入数组的所有元素进行排序。 2） 使用两个索引变量l和r分别从左端和右端进行遍历。将l初始化为0，将r初始化为n-1。 3） 总和=a[l]+a[r] 4） 如果sum是-ve，那么l++ 5） 如果总和是+ve，那么r—— 6） 跟踪abs最小和。 7） 在l
实施
C++
#include <bits/stdc++.h> using namespace std; void quickSort( int *, int , int ); /* Function to print pair of elements having minimum sum */ void minAbsSumPair( int arr[], int n) { // Variables to keep track // of current sum and minimum sum int sum, min_sum = INT_MAX; // left and right index variables int l = 0, r = n-1; // variable to keep track of // the left and right pair for min_sum int min_l = l, min_r = n-1; /* Array should have at least two elements*/ if (n < 2) { cout << "Invalid Input" ; return ; } /* Sort the elements */ quickSort(arr, l, r); while (l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less then update the result items*/ if ( abs (sum) < abs (min_sum)) { min_sum = sum; min_l = l; min_r = r; } if (sum < 0) l++; else r--; } cout << "The two elements whose sum is minimum are " << arr[min_l] << " and " << arr[min_r]; } // Driver Code int main() { int arr[] = {1, 60, -10, 70, -80, 85}; int n = sizeof (arr) / sizeof (arr[0]); minAbsSumPair(arr, n); return 0; } /* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING PURPOSE */ void exchange( int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int partition( int arr[], int si, int ei) { int x = arr[ei]; int i = (si - 1); int j; for (j = si; j <= ei - 1; j++) { if (arr[j] <= x) { i++; exchange(&arr[i], &arr[j]); } } exchange (&arr[i + 1], &arr[ei]); return (i + 1); } /* Implementation of Quick Sort arr[] --> Array to be sorted si --> Starting index ei --> Ending index */ void quickSort( int arr[], int si, int ei) { int pi; /* Partitioning index */ if (si < ei) { pi = partition(arr, si, ei); quickSort(arr, si, pi - 1); quickSort(arr, pi + 1, ei); } } // This code is contributed by rathbhupendra |
C
# include <stdio.h> # include <math.h> # include <limits.h> void quickSort( int *, int , int ); /* Function to print pair of elements having minimum sum */ void minAbsSumPair( int arr[], int n) { // Variables to keep track of current sum and minimum sum int sum, min_sum = INT_MAX; // left and right index variables int l = 0, r = n-1; // variable to keep track of the left and right pair for min_sum int min_l = l, min_r = n-1; /* Array should have at least two elements*/ if (n < 2) { printf ( "Invalid Input" ); return ; } /* Sort the elements */ quickSort(arr, l, r); while (l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less then update the result items*/ if ( abs (sum) < abs (min_sum)) { min_sum = sum; min_l = l; min_r = r; } if (sum < 0) l++; else r--; } printf ( " The two elements whose sum is minimum are %d and %d" , arr[min_l], arr[min_r]); } /* Driver program to test above function */ int main() { int arr[] = {1, 60, -10, 70, -80, 85}; int n = sizeof (arr)/ sizeof (arr[0]); minAbsSumPair(arr, n); getchar (); return 0; } /* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING PURPOSE */ void exchange( int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int partition( int arr[], int si, int ei) { int x = arr[ei]; int i = (si - 1); int j; for (j = si; j <= ei - 1; j++) { if (arr[j] <= x) { i++; exchange(&arr[i], &arr[j]); } } exchange (&arr[i + 1], &arr[ei]); return (i + 1); } /* Implementation of Quick Sort arr[] --> Array to be sorted si --> Starting index ei --> Ending index */ void quickSort( int arr[], int si, int ei) { int pi; /* Partitioning index */ if (si < ei) { pi = partition(arr, si, ei); quickSort(arr, si, pi - 1); quickSort(arr, pi + 1, ei); } } |
JAVA
import java.util.*; import java.lang.*; class Main { static void minAbsSumPair( int arr[], int n) { // Variables to keep track of current sum and minimum sum int sum, min_sum = 999999 ; // left and right index variables int l = 0 , r = n- 1 ; // variable to keep track of the left and right pair for min_sum int min_l = l, min_r = n- 1 ; /* Array should have at least two elements*/ if (n < 2 ) { System.out.println( "Invalid Input" ); return ; } /* Sort the elements */ sort(arr, l, r); while (l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less then update the result items*/ if (Math.abs(sum) < Math.abs(min_sum)) { min_sum = sum; min_l = l; min_r = r; } if (sum < 0 ) l++; else r--; } System.out.println( " The two elements whose " + "sum is minimum are " + arr[min_l]+ " and " +arr[min_r]); } // main function public static void main (String[] args) { int arr[] = { 1 , 60 , - 10 , 70 , - 80 , 85 }; int n = arr.length; minAbsSumPair(arr, n); } /* Functions for QuickSort */ /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ static int partition( int arr[], int low, int high) { int pivot = arr[high]; int i = (low- 1 ); // index of smaller element for ( int j=low; j<high; j++) { // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // swap arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // swap arr[i+1] and arr[high] (or pivot) int temp = arr[i+ 1 ]; arr[i+ 1 ] = arr[high]; arr[high] = temp; return i+ 1 ; } /* The main function that implements QuickSort() arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */ static void sort( int arr[], int low, int high) { if (low < high) { /* pi is partitioning index, arr[pi] is now at right place */ int pi = partition(arr, low, high); // Recursively sort elements before // partition and after partition sort(arr, low, pi- 1 ); sort(arr, pi+ 1 , high); } } } |
蟒蛇3
# Function to print pair of elements # having minimum sum */ # FOLLOWING FUNCTIONS ARE ONLY FOR # SORTING PURPOSE */ def partition(arr, si, ei): x = arr[ei] i = (si - 1 ) for j in range (si,ei): if (arr[j] < = x): i + = 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1 ], arr[ei] = arr[ei], arr[i + 1 ] return (i + 1 ) # Implementation of Quick Sort # arr[] --> Array to be sorted # si --> Starting index # ei --> Ending index def quickSort(arr, si, ei): pi = 0 # Partitioning index */ if (si < ei): pi = partition(arr, si, ei) quickSort(arr, si, pi - 1 ) quickSort(arr, pi + 1 , ei) def minAbsSumPair(arr, n): # Variables to keep track # of current sum and minimum sum sum , min_sum = 0 , 10 * * 9 # left and right index variables l = 0 r = n - 1 # variable to keep track of # the left and right pair for min_sum min_l = l min_r = n - 1 # Array should have at least two elements*/ if (n < 2 ): print ( "Invalid Input" , end = "") return # Sort the elements */ quickSort(arr, l, r) while (l < r): sum = arr[l] + arr[r] # If abs(sum) is less # then update the result items if ( abs ( sum ) < abs (min_sum)): min_sum = sum min_l = l min_r = r if ( sum < 0 ): l + = 1 else : r - = 1 print ( "The two elements whose sum is minimum are" , arr[min_l], "and" , arr[min_r]) # Driver Code arr = [ 1 , 60 , - 10 , 70 , - 80 , 85 ] n = len (arr) minAbsSumPair(arr, n) # This code is contributed by mohit kumar 29 |
C#
using System; class GFG { static void minAbsSumPair( int []arr , int n) { // Variables to keep track // of current sum and minimum sum int sum, min_sum = 999999; // left and right index variables int l = 0, r = n-1; // variable to keep track of the left // and right pair for min_sum int min_l = l, min_r = n-1; /* Array should have at least two elements*/ if (n < 2) { Console.Write( "Invalid Input" ); return ; } /* Sort the elements */ sort(arr, l, r); while (l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less then update the result items*/ if (Math.Abs(sum) < Math.Abs(min_sum)) { min_sum = sum; min_l = l; min_r = r; } if (sum < 0) l++; else r--; } Console.Write( " The two elements whose " + "sum is minimum are " + arr[min_l]+ " and " + arr[min_r]); } // driver code public static void Main () { int []arr = {1, 60, -10, 70, -80, 85}; int n = arr.Length; minAbsSumPair(arr, n); } /* Functions for QuickSort */ /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ static int partition( int []arr, int low, int high) { int pivot = arr[high]; int i = (low-1); // index of smaller element for ( int j = low; j < high; j++) { // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // swap arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // swap arr[i+1] and arr[high] (or pivot) int temp1 = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp1; return i+1; } /* The main function that implements QuickSort() arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */ static void sort( int []arr, int low, int high) { if (low < high) { /* pi is partitioning index, arr[pi] is now at right place */ int pi = partition(arr, low, high); // Recursively sort elements before // partition and after partition sort(arr, low, pi-1); sort(arr, pi+1, high); } } } // This code is contributed by Sam007 |
Javascript
<script> function minAbsSumPair(arr,n) { // Variables to keep track of current sum and minimum sum let sum, min_sum = 999999; // left and right index variables let l = 0, r = n-1; // variable to keep track of the left and right pair for min_sum let min_l = l, min_r = n-1; /* Array should have at least two elements*/ if (n < 2) { document.write( "Invalid Input" ); return ; } /* Sort the elements */ sort(arr, l, r); while (l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less then update the result items*/ if (Math.abs(sum) < Math.abs(min_sum)) { min_sum = sum; min_l = l; min_r = r; } if (sum < 0) l++; else r--; } document.write( " The two elements whose " + "sum is minimum are " + arr[min_l]+ " and " +arr[min_r]); } /* Functions for QuickSort */ /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ function partition(arr,low,high) { let pivot = arr[high]; let i = (low-1); // index of smaller element for (let j=low; j<high; j++) { // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // swap arr[i] and arr[j] let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // swap arr[i+1] and arr[high] (or pivot) let temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; } /* The main function that implements QuickSort() arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */ function sort(arr,low,high) { if (low < high) { /* pi is partitioning index, arr[pi] is now at right place */ let pi = partition(arr, low, high); // Recursively sort elements before // partition and after partition sort(arr, low, pi-1); sort(arr, pi+1, high); } } // main function let arr=[1, 60, -10, 70, -80, 85]; let n = arr.length; minAbsSumPair(arr, n); // This code is contributed by unknown2108 </script> |
输出：
The two elements whose sum is minimum are -80 and 85
时间复杂性： 排序的复杂性+找到最佳对的复杂性=O（nlogn）+O（n）=O（nlogn）
方法2的STL实现 :
算法 1） 使用绝对值对输入数组的所有元素进行排序。 2） 检查arr[i-1]和arr[i]的绝对和，如果它们的绝对和小于min，则用它们的绝对值更新min。 3） 使用两个变量来存储元素的索引。
实施
C++
// C++ implementation using STL #include <bits/stdc++.h> using namespace std; // Modified to sort by absolute values bool compare( int x, int y) { return abs (x) < abs (y); } void findMinSum( int arr[], int n) { sort(arr, arr + n, compare); int min = INT_MAX, x, y; for ( int i = 1; i < n; i++) { // Absolute value shows how close it is to zero if ( abs (arr[i - 1] + arr[i]) <= min) { // if found an even close value // update min and store the index min = abs (arr[i - 1] + arr[i]); x = i - 1; y = i; } } cout << "The two elements whose sum is minimum are " << arr[x] << " and " << arr[y]; } // Driver code int main() { int arr[] = { 1, 60, -10, 70, -80, 85 }; int n = sizeof (arr) / sizeof (arr[0]); findMinSum(arr, n); return 0; // This code is contributed by ceeyesharish } |
JAVA
// Java implementation using STL import java.io.*; class GFG{ static void findMinSum( int [] arr, int n) { for ( int i = 1 ; i < n; i++) { if (!(Math.abs(arr[i - 1 ]) < Math.abs(arr[i]))) { int temp = arr[i - 1 ]; arr[i - 1 ] = arr[i]; arr[i] = temp; } } int min = Integer.MAX_VALUE; int x = 0 , y = 0 ; for ( int i = 1 ; i < n; i++) { // Absolute value shows how close // it is to zero if (Math.abs(arr[i - 1 ] + arr[i]) <= min) { // If found an even close value // update min and store the index min = Math.abs(arr[i - 1 ] + arr[i]); x = i - 1 ; y = i; } } System.out.println( "The two elements whose " + "sum is minimum are " + arr[x] + " and " + arr[y]); } // Driver code public static void main(String[] args) { int [] arr = { 1 , 60 , - 10 , 70 , - 80 , 85 }; int n = arr.length; findMinSum(arr, n); } } // This code is contributed by rag2127 |
蟒蛇3
# Python3 implementation using STL import sys def findMinSum(arr, n): for i in range ( 1 , n): # Modified to sort by absolute values if ( not abs (arr[i - 1 ]) < abs (arr[i])): arr[i - 1 ], arr[i] = arr[i], arr[i - 1 ] Min = sys.maxsize x = 0 y = 0 for i in range ( 1 , n): # Absolute value shows how # close it is to zero if ( abs (arr[i - 1 ] + arr[i]) < = Min ): # If found an even close value # update min and store the index Min = abs (arr[i - 1 ] + arr[i]) x = i - 1 y = i print ( "The two elements whose sum is minimum are" , arr[x], "and" , arr[y]) # Driver code arr = [ 1 , 60 , - 10 , 70 , - 80 , 85 ] n = len (arr) findMinSum(arr, n) # This code is contributed by avanitrachhadiya2155 |
C#
// C# implementation using STL using System; class GFG{ static void findMinSum( int [] arr, int n) { for ( int i = 1; i < n; i++) { if (!(Math.Abs(arr[i - 1]) < Math.Abs(arr[i]))) { int temp = arr[i - 1]; arr[i - 1] = arr[i]; arr[i] = temp; } } int min = Int32.MaxValue; int x = 0, y = 0; for ( int i = 1; i < n; i++) { // Absolute value shows how close // it is to zero if (Math.Abs(arr[i - 1] + arr[i]) <= min) { // If found an even close value // update min and store the index min = Math.Abs(arr[i - 1] + arr[i]); x = i - 1; y = i; } } Console.WriteLine( "The two elements whose " + "sum is minimum are " + arr[x] + " and " + arr[y]); } // Driver Code static void Main() { int [] arr = { 1, 60, -10, 70, -80, 85 }; int n = arr.Length; findMinSum(arr, n); } } // This code is contributed by divyesh072019 |
Javascript
<script> // Javascript implementation using STL function findMinSum(arr, n) { for (let i = 1; i < n; i++) { if (!(Math.abs(arr[i - 1]) < Math.abs(arr[i]))) { let temp = arr[i - 1]; arr[i - 1] = arr[i]; arr[i] = temp; } } let min = Number.MAX_VALUE; let x = 0, y = 0; for (let i = 1; i < n; i++) { // Absolute value shows how close // it is to zero if (Math.abs(arr[i - 1] + arr[i]) <= min) { // If found an even close value // update min and store the index min = Math.abs(arr[i - 1] + arr[i]); x = i - 1; y = i; } } document.write( "The two elements whose " + "sum is minimum are " + arr[x] + " and " + arr[y]); } // Driver code let arr = [ 1, 60, -10, 70, -80, 85 ]; let n = arr.length; findMinSum(arr, n); // This code is contributed by suresh07 </script> |
输出：
The two elements whose sum is minimum are -80 and 85
时间复杂度：O（nlogn） 空间复杂性：O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
