给定一个未排序的数组 arr[] 还有两个数字 十、 和 Y ，找到之间的最小距离 十、 和 Y 在里面 arr[] 。该数组也可能包含重复项。你可以假设两者 十、 和 Y 是不同的，存在于 arr[] .
null
例如：
Input: arr[] = {1, 2}, x = 1, y = 2Output: Minimum distance between 1 and 2 is 1.Explanation: 1 is at index 0 and 2 is at index 1, so the distance is 1Input: arr[] = {3, 4, 5}, x = 3, y = 5Output: Minimum distance between 3 and 5 is 2.Explanation:3 is at index 0 and 5 is at index 2, so the distance is 2Input: arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}, x = 3, y = 6Output: Minimum distance between 3 and 6 is 4.Explanation:3 is at index 0 and 6 is at index 5, so the distance is 4Input: arr[] = {2, 5, 3, 5, 4, 4, 2, 3}, x = 3, y = 2Output: Minimum distance between 3 and 2 is 1.Explanation:3 is at index 7 and 2 is at index 6, so the distance is 1
方法1：
- 方法： 任务是找到两个给定数字之间的距离，所以使用嵌套循环找到任意两个元素之间的距离。外循环用于选择第一个元素（x），内循环用于遍历数组以搜索另一个元素（y），并获取它们之间的最小距离。
- 算法：
- 创建一个变量 m=INT_MAX
- 运行一个嵌套循环，外部循环从开始运行到结束（循环计数器i），内部循环从i+1运行到结束（循环计数器j）。
- 如果第i个元素是x，第j个元素是y，反之亦然，则将m更新为 m=最小值（m，j-i）
- 将m的值打印为最小距离
- 实施：
C++
// C++ program to Find the minimum // distance between two numbers #include <bits/stdc++.h> using namespace std; int minDist( int arr[], int n, int x, int y) { int i, j; int min_dist = INT_MAX; for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if ((x == arr[i] && y == arr[j] || y == arr[i] && x == arr[j]) && min_dist > abs (i - j)) { min_dist = abs (i - j); } } } if (min_dist > n) { return -1; } return min_dist; } /* Driver code */ int main() { int arr[] = { 3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3 }; int n = sizeof (arr) / sizeof (arr[0]); int x = 3; int y = 6; cout << "Minimum distance between " << x << " and " << y << " is " << minDist(arr, n, x, y) << endl; } // This code is contributed by Shivi_Aggarwal |
C
// C program to Find the minimum // distance between two numbers #include <limits.h> // for INT_MAX #include <stdio.h> #include <stdlib.h> // for abs() int minDist( int arr[], int n, int x, int y) { int i, j; int min_dist = INT_MAX; for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if ((x == arr[i] && y == arr[j] || y == arr[i] && x == arr[j]) && min_dist > abs (i - j)) { min_dist = abs (i - j); } } } if (min_dist > n) { return -1; } return min_dist; } /* Driver program to test above function */ int main() { int arr[] = { 3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3 }; int n = sizeof (arr) / sizeof (arr[0]); int x = 0; int y = 6; printf ( "Minimum distance between %d and %d is %d" , x, y, minDist(arr, n, x, y)); return 0; } |
JAVA
// Java Program to Find the minimum // distance between two numbers class MinimumDistance { int minDist( int arr[], int n, int x, int y) { int i, j; int min_dist = Integer.MAX_VALUE; for (i = 0 ; i < n; i++) { for (j = i + 1 ; j < n; j++) { if ((x == arr[i] && y == arr[j] || y == arr[i] && x == arr[j]) && min_dist > Math.abs(i - j)) min_dist = Math.abs(i - j); } } if (min_dist > n) { return - 1 ; } return min_dist; } public static void main(String[] args) { MinimumDistance min = new MinimumDistance(); int arr[] = { 3 , 5 , 4 , 2 , 6 , 5 , 6 , 6 , 5 , 4 , 8 , 3 }; int n = arr.length; int x = 0 ; int y = 6 ; System.out.println( "Minimum distance between " + x + " and " + y + " is " + min.minDist(arr, n, x, y)); } } |
Python3
# Python3 code to Find the minimum # distance between two numbers def minDist(arr, n, x, y): min_dist = 99999999 for i in range (n): for j in range (i + 1 , n): if (x = = arr[i] and y = = arr[j] or y = = arr[i] and x = = arr[j]) and min_dist > abs (i - j): min_dist = abs (i - j) return min_dist # Driver code arr = [ 3 , 5 , 4 , 2 , 6 , 5 , 6 , 6 , 5 , 4 , 8 , 3 ] n = len (arr) x = 3 y = 6 print ( "Minimum distance between " , x, " and " , y, "is" , minDist(arr, n, x, y)) # This code is contributed by "Abhishek Sharma 44" |
C#
// C# code to Find the minimum // distance between two numbers using System; class GFG { static int minDist( int []arr, int n, int x, int y) { int i, j; int min_dist = int .MaxValue; for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if ((x == arr[i] && y == arr[j] || y == arr[i] && x == arr[j]) && min_dist > Math.Abs(i - j)) min_dist = Math.Abs(i - j); } } return min_dist; } // Driver function public static void Main() { int []arr = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}; int n = arr.Length; int x = 3; int y = 6; Console.WriteLine( "Minimum " + "distance between " + x + " and " + y + " is " + minDist(arr, n, x, y)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to Find the minimum // distance between two numbers function minDist( $arr , $n , $x , $y ) { $i ; $j ; $min_dist = PHP_INT_MAX; for ( $i = 0; $i < $n ; $i ++) { for ( $j = $i + 1; $j < $n ; $j ++) { if ( ( $x == $arr [ $i ] and $y == $arr [ $j ] or $y == $arr [ $i ] and $x == $arr [ $j ]) and $min_dist > abs ( $i - $j )) { $min_dist = abs ( $i - $j ); } } } if ( $min_dist > $n ) { return -1; } return $min_dist ; } // Driver Code $arr = array (3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3); $n = count ( $arr ); $x = 0; $y = 6; echo "Minimum distance between " , $x , " and " , $y , " is " ; echo minDist( $arr , $n , $x , $y ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find the minimum // distance between two numbers function minDist(arr, n, x, y) { var i, j; var min_dist = Number.MAX_VALUE; for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if ((x == arr[i] && y == arr[j] || y == arr[i] && x == arr[j]) && min_dist > Math.abs(i - j)) min_dist = Math.abs(i - j); } } if (min_dist>n) { return -1; } return min_dist; } // Driver code var arr = [ 3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3 ]; var n = arr.length; var x = 3; var y = 6; document.write( "Minimum distance between " + x + " and " + y + " is " + minDist(arr, n, x, y)); // This code is contributed by gauravrajput1 </script> |
输出
Minimum distance between 3 and 6 is 4
- 复杂性分析：
- 时间复杂性： O（n^2），嵌套循环用于遍历数组。
- 空间复杂性： O（1），不需要额外的空间。
方法2：
- 方法： 因此，基本方法是只检查x和y的连续对。对于每个元素x或y，检查之前出现的x或y的索引，如果之前出现的元素与当前元素不相似，则更新最小距离。但是一个问题出现了，如果一个x前面有另一个x，而这个x前面有一个y，那么如何获得对之间的最小距离呢。通过仔细分析可以看出，每个x后面跟一个y，或者y后面跟一个y，都只能是最近的对（最小距离），所以忽略所有其他对。
- 算法：
- 创建一个变量 prev=-1 和 m=INT_MAX
- 从头到尾遍历阵列。
- 如果当前元素为x或y，prev不等于-1，且数组[prev]不等于当前元素，则更新m=max（当前_索引–prev，m），即找到连续对之间的距离，并用它更新m。
- 打印m的值
- 感谢wgpshashank提出了这种方法。
![图片[1]-求两个数字之间的最小距离-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/20200302163600/gif2.gif)
- 实施
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; int minDist( int arr[], int n, int x, int y) { //previous index and min distance int p = -1, min_dist = INT_MAX; for ( int i=0 ; i<n ; i++) { if (arr[i]==x || arr[i]==y) { //we will check if p is not equal to -1 and //If the element at current index matches with //the element at index p , If yes then update //the minimum distance if needed if ( p != -1 && arr[i] != arr[p]) min_dist = min(min_dist , i-p); //update the previous index p=i; } } //If distance is equal to int max if (min_dist==INT_MAX) return -1; return min_dist; } /* Driver code */ int main() { int arr[] = {3, 5, 4, 2, 6, 3, 0, 0, 5, 4, 8, 3}; int n = sizeof (arr) / sizeof (arr[0]); int x = 3; int y = 6; cout << "Minimum distance between " << x << " and " << y << " is " << minDist(arr, n, x, y) << endl; return 0; } // This code is contributed by Mukul singh. |
C
#include <stdio.h> #include <limits.h> // For INT_MAX //returns minimum of two numbers int min( int a , int b) { if (a < b) return a; return b; } int minDist( int arr[], int n, int x, int y) { //previous index and min distance int i=0,p=-1, min_dist=INT_MAX; for (i=0 ; i<n ; i++) { if (arr[i] ==x || arr[i] == y) { //we will check if p is not equal to -1 and //If the element at current index matches with //the element at index p , If yes then update //the minimum distance if needed if (p != -1 && arr[i] != arr[p]) min_dist = min(min_dist,i-p); //update the previous index p=i; } } //If distance is equal to int max if (min_dist==INT_MAX) return -1; return min_dist; } /* Driver program to test above function */ int main() { int arr[] ={3, 5, 4, 2, 6, 3, 0, 0, 5, 4, 8, 3}; int n = sizeof (arr)/ sizeof (arr[0]); int x = 3; int y = 6; printf ( "Minimum distance between %d and %d is %d" , x, y, minDist(arr, n, x, y)); return 0; } |
JAVA
class MinimumDistance { int minDist( int arr[], int n, int x, int y) { //previous index and min distance int i= 0 ,p=- 1 , min_dist=Integer.MAX_VALUE; for (i= 0 ; i<n ; i++) { if (arr[i] ==x || arr[i] == y) { //we will check if p is not equal to -1 and //If the element at current index matches with //the element at index p , If yes then update //the minimum distance if needed if (p != - 1 && arr[i] != arr[p]) min_dist = Math.min(min_dist,i-p); //update the previous index p=i; } } //If distance is equal to int max if (min_dist==Integer.MAX_VALUE) return - 1 ; return min_dist; } /* Driver program to test above functions */ public static void main(String[] args) { MinimumDistance min = new MinimumDistance(); int arr[] = { 3 , 5 , 4 , 2 , 6 , 3 , 0 , 0 , 5 , 4 , 8 , 3 }; int n = arr.length; int x = 3 ; int y = 6 ; System.out.println( "Minimum distance between " + x + " and " + y + " is " + min.minDist(arr, n, x, y)); } } |
Python3
import sys def minDist(arr, n, x, y): #previous index and min distance i = 0 p = - 1 min_dist = sys.maxsize; for i in range (n): if (arr[i] = = x or arr[i] = = y): #we will check if p is not equal to -1 and #If the element at current index matches with #the element at index p , If yes then update #the minimum distance if needed if (p ! = - 1 and arr[i] ! = arr[p]): min_dist = min (min_dist,i - p) #update the previous index p = i #If distance is equal to int max if (min_dist = = sys.maxsize): return - 1 return min_dist # Driver program to test above function */ arr = [ 3 , 5 , 4 , 2 , 6 , 3 , 0 , 0 , 5 , 4 , 8 , 3 ] n = len (arr) x = 3 y = 6 print ( "Minimum distance between %d and %d is %d" % ( x, y,minDist(arr, n, x, y))); # This code is contributed by Shreyanshi Arun. |
C#
// C# program to Find the minimum // distance between two numbers using System; class MinimumDistance { static int minDist( int []arr, int n, int x, int y) { //previous index and min distance int i=0,p=-1, min_dist= int .MaxValue; for (i=0 ; i<n ; i++) { if (arr[i] ==x || arr[i] == y) { //we will check if p is not equal to -1 and //If the element at current index matches with //the element at index p , If yes then update //the minimum distance if needed if (p != -1 && arr[i] != arr[p]) min_dist = Math.Min(min_dist,i-p); //update the previous index p=i; } } //If distance is equal to int max if (min_dist== int .MaxValue) return -1; return min_dist; } // Driver Code public static void Main() { int []arr = {3, 5, 4, 2, 6, 3, 0, 0, 5, 4, 8, 3}; int n = arr.Length; int x = 3; int y = 6; Console.WriteLine( "Minimum distance between " + x + " and " + y + " is " + minDist(arr, n, x, y)); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP program to Find the minimum // distance between two numbers function minDist( $arr , $n , $x , $y ) { //previous index and min distance $i =0; $p =-1; $min_dist =PHP_INT_MAX; for ( $i =0 ; $i < $n ; $i ++) { if ( $arr [ $i ] == $x || $arr [ $i ] == $y ) { //we will check if p is not equal to -1 and //If the element at current index matches with //the element at index p , If yes then update //the minimum distance if needed if ( $p != -1 && $arr [ $i ] != $arr [ $p ]) $min_dist = min( $min_dist , $i - $p ); //update the previous index $p = $i ; } } //If distance is equal to int max if ( $min_dist ==PHP_INT_MAX) return -1; return $min_dist ; } /* Driver program to test above function */ $arr = array (3, 5, 4, 2, 6, 3, 0, 0, 5, 4, 8, 3); $n = count ( $arr ); $x = 3; $y = 6; echo "Minimum distance between $x and " , "$y is " , minDist( $arr , $n , $x , $y ); // This code is contributed by anuj_67. ?> |
Javascript
<script> function minDist(arr , n , x , y) { // previous index and min distance var i=0,p=-1, min_dist=Number.MAX_VALUE; for (i=0 ; i<n ; i++) { if (arr[i] ==x || arr[i] == y) { // we will check if p is not equal to -1 and // If the element at current index matches with // the element at index p , If yes then update // the minimum distance if needed if (p != -1 && arr[i] != arr[p]) min_dist = Math.min(min_dist,i-p); // update the previous index p=i; } } // If distance is equal to var max if (min_dist==Number.MAX_VALUE) return -1; return min_dist; } /* Driver program to test above functions */ var arr = [3, 5, 4, 2, 6, 3, 0, 0, 5, 4, 8, 3]; var n = arr.length; var x = 3; var y = 6; document.write( "Minimum distance between " + x + " and " + y + " is " + minDist(arr, n, x, y)); // This code contributed by shikhasingrajput </script> |
输出
Minimum distance between 3 and 6 is 1
- 复杂性分析：
- 时间复杂性： O（n）。 只需要遍历数组一次。
- 空间复杂性： O（1）。 因为不需要额外的空间。
如果您发现上述代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
