未排序整数列表中最接近的数字-yiteyi-C++库

给定一个不同的未排序整数列表，找出它们之间绝对差值最小的元素对？如果有多对，请全部找到。例如：

null

Input : arr[] = {10, 50, 12, 100}Output : (10, 12)The closest elements are 10 and 12Input : arr[] = {5, 4, 3, 2}Output : (2, 3), (3, 4), (4, 5)

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个问题主要是找出任意两个元素之间的最小差异 .

对给定数组进行排序。
求排序数组中线性时间内所有对的最小差。
再次遍历排序数组一次，以打印步骤2中获得的最小差异的所有对。

C++

                         // CPP program to find minimum difference                       
                         // an unsorted array.                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns minimum difference between any                       
                         // two pair in arr[0..n-1]                       
                         void                                     printMinDiffPairs(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 if                                     (n <= 1)                       
                                                 return                                     ;                       
           
                                                 // Sort array elements                       
                                                 sort(arr, arr+n);                       
           
                                                 // Compare differences of adjacent                       
                                                 // pairs to find the minimum difference.                       
                                                 int                                     minDiff = arr[1] - arr[0];                       
                                                 for                                     (                                     int                                     i = 2 ; i < n ; i++)                       
                                                 minDiff = min(minDiff, arr[i] - arr[i-1]);                       
           
                                                 // Traverse array again and print all pairs                       
                                                 // with difference as minDiff.                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 if                                     ((arr[i] - arr[i-1]) == minDiff)                       
                                                 cout <<                                     "("                                     << arr[i-1] <<                                     ", "                       
                                                 << arr[i] <<                                     "), "                                     ;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {5, 3, 2, 4, 1};                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 printMinDiffPairs(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find minimum                       
                         // difference an unsorted array.                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                                                 // Returns minimum difference between                       
                                                 // any two pair in arr[0..n-1]                       
                                                 static                                     void                                     printMinDiffPairs(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n <=                                     1                                     )                       
                                                 return                                     ;                       
                                   
                                                 // Sort array elements                       
                                                 Arrays.sort(arr);                       
                                   
                                                 // Compare differences of adjacent                       
                                                 // pairs to find the minimum difference.                       
                                                 int                                     minDiff = arr[                                     1                                     ] - arr[                                     0                                     ];                       
                                                 for                                     (                                     int                                     i =                                     2                                     ; i < n; i++)                       
                                                 minDiff = Math.min(minDiff, arr[i] - arr[i-                                     1                                     ]);                       
                                   
                                                 // Traverse array again and print all pairs                       
                                                 // with difference as minDiff.                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++)                       
                                                 {                       
                                                 if                                     ((arr[i] - arr[i-                                     1                                     ]) == minDiff)                       
                                                 {                       
                                                 System.out.print(                                     "("                                     + arr[i-                                     1                                     ] +                                     ", "                       
                                                 + arr[i] +                                     "),"                                     );                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     5                                     ,                                     3                                     ,                                     2                                     ,                                     4                                     ,                                     1                                     };                       
                                                 int                                     n = arr.length;                       
                                                 printMinDiffPairs(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Ansu Kumari                       

Python3

                         # Python3 program to find minimum                       
                         # difference in an unsorted array.                       
           
                         # Returns minimum difference between                       
                         # any two pair in arr[0..n-1]                       
                         def                                     printMinDiffPairs(arr , n):                       
                                                 if                                     n <                                     =                                     1                                     :                                     return                       
           
                                                 # Sort array elements                       
                                                 arr.sort()                       
                                   
                                                 # Compare differences of adjacent                       
                                                 # pairs to find the minimum difference.                       
                                                 minDiff                                     =                                     arr[                                     1                                     ]                                     -                                     arr[                                     0                                     ]                       
                                                 for                                     i                                     in                                     range                                     (                                     2                                     , n):                       
                                                 minDiff                                     =                                     min                                     (minDiff, arr[i]                                     -                                     arr[i                                     -                                     1                                     ])                       
           
                                                 # Traverse array again and print all                       
                                                 # pairs with difference as minDiff.                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                                 if                                     (arr[i]                                     -                                     arr[i                                     -                                     1                                     ])                                     =                                     =                                     minDiff:                       
                                                 print                                     (                                     "("                                     +                                     str                                     (arr[i                                     -                                     1                                     ])                                     +                                     ", "                       
                                                 +                                     str                                     (arr[i])                                     +                                     "), "                                     , end                                     =                                     '')                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     5                                     ,                                     3                                     ,                                     2                                     ,                                     4                                     ,                                     1                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         printMinDiffPairs(arr , n)                       
           
                         # This code is contributed by Ansu Kumari                       

C#

                         // C# program to find minimum                       
                         // difference an unsorted array.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Returns minimum difference between                       
                         // any two pair in arr[0..n-1]                       
                         static                                     void                                     printMinDiffPairs(                                     int                                     []arr,                                     int                                     n)                       
                         {                       
                                                 if                                     (n <= 1)                       
                                                 return                                     ;                       
                                   
                                                 // Sort array elements                       
                                                 Array.Sort(arr);                       
                                   
                                                 // Compare differences of adjacent                       
                                                 // pairs to find the minimum difference.                       
                                                 int                                     minDiff = arr[1] - arr[0];                       
                                                 for                                     (                                     int                                     i = 2; i < n; i++)                       
                                                 minDiff = Math.Min(minDiff, arr[i] - arr[i-1]);                       
                                   
                                                 // Traverse array again and print all pairs                       
                                                 // with difference as minDiff.                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 if                                     ((arr[i] - arr[i-1]) == minDiff)                       
                                                 {                       
                                                 Console.Write(                                     " ("                                     + arr[i-1] +                                     ", "                       
                                                 + arr[i] +                                     "), "                                     );                       
                                                 }                       
                                                 }                       
                         }                       
                                   
                         // Driver code                       
                         public                                     static                                     void                                     Main ()                       
                         {                       
                                                 int                                     []arr = {5, 3, 2, 4, 1};                       
                                                 int                                     n = arr.Length;                       
                                                 printMinDiffPairs(arr, n);                       
                         }                       
                         }                       
           
                         // This code is contributed by vt_m                       

PHP

                         <?php                       
                         //PHP program to find minimum difference                       
                         // an unsorted array.                       
           
                         // Returns minimum difference between any                       
                         // two pair in arr[0..n-1]                       
                         function                                     printMinDiffPairs(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 if                                     (                                     $n                                     <= 1)                       
                                                 return                                     ;                       
                                   
                                                 // Sort array elements                       
                                                 sort(                                     $arr                                     );                       
                                   
                                                 // Compare differences of adjacent                       
                                                 // pairs to find the minimum                       
                                                 // difference.                       
                                                 $minDiff                                     =                                     $arr                                     [1] -                                     $arr                                     [0];                       
                                   
                                                 for                                     (                                     $i                                     = 2 ;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $minDiff                                     = min(                                     $minDiff                                     ,                                     $arr                                     [                                     $i                                     ]                       
                                                 -                                     $arr                                     [                                     $i                                     -1]);                       
                                   
                                                 // Traverse array again and print all                       
                                                 // pairs with difference as minDiff.                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 if                                     ((                                     $arr                                     [                                     $i                                     ] -                                     $arr                                     [                                     $i                                     -1]) ==                       
                                                 $minDiff                                     )                       
                                                 echo                                     "("                                     ,                                     $arr                                     [                                     $i                                     -1] ,                                     ", "                                     ,                       
                                                 $arr                                     [                                     $i                                     ] ,                                     "), "                                     ;                       
                         }                       
           
                         // Driver code                       
                                                 $arr                                     =                                     array                                     (5, 3, 2, 4, 1);                       
                                                 $n                                     = sizeof(                                     $arr                                     );                       
                                                 printMinDiffPairs(                                     $arr                                     ,                                     $n                                     );                       
                                   
                         // This code is contributed by ajit.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to find minimum                       
                         // difference an unsorted array.                       
           
                                                 // Returns minimum difference between                       
                                                 // any two pair in arr[0..n-1]                       
                                                 function                                     printMinDiffPairs(arr, n)                       
                                                 {                       
                                                 if                                     (n <= 1)                       
                                                 return                                     ;                       
                                   
                                                 // Sort array elements                       
                                                 arr.sort();                       
                                   
                                                 // Compare differences of adjacent                       
                                                 // pairs to find the minimum difference.                       
                                                 let minDiff = arr[1] - arr[0];                       
                                                 for                                     (let i = 2; i < n; i++)                       
                                                 minDiff = Math.min(minDiff, arr[i] - arr[i-1]);                       
                                   
                                                 // Traverse array again and print all pairs                       
                                                 // with difference as minDiff.                       
                                                 for                                     ( let i = 1; i < n; i++)                       
                                                 {                       
                                                 if                                     ((arr[i] - arr[i-1]) == minDiff)                       
                                                 {                       
                                                 document.write(                                     "("                                     + arr[i-1] +                                     ", "                       
                                                 + arr[i] +                                     ") , "                                     );                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
           
                         // Driver code                       
                                   
                                                 let arr = [5, 3, 2, 4, 1];                       
                                                 let n = arr.length;                       
                                                 printMinDiffPairs(arr , n);                       
           
                         </script>                       

输出：

(1, 2), (2, 3), (3, 4), (4, 5),

上面的程序处理重复的吗？ 类似{x，x，x}的情况不由上述程序处理。对于这种情况，预期输出（x，x），（x，x），（x，x），但上面的程序打印（x，x），（x，x）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章