找到两个数字之间的最小距离
原文： https://www.geeksforgeeks.org/find-the-minimum-distance-between-two-numbers/
给定未排序的数组arr[]和两个数字x和y，找出x和y在arr[]中的最小距离。 数组也可能包含重复项。 您可以假设x和y都不相同，并且存在于arr[]中。
示例：
Input: arr[] = {1, 2}, x = 1, y = 2
Output: Minimum distance between 1
and 2 is 1.
Explanation: 1 is at index 0 and 2 is at
index 1, so the distance is 1
Input: arr[] = {3, 4, 5}, x = 3, y = 5
Output: Minimum distance between 3
and 5 is 2.
Explanation:3 is at index 0 and 5 is at
index 2, so the distance is 2
Input:
arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3},
x = 3, y = 6
Output: Minimum distance between 3
and 6 is 4.
Explanation:3 is at index 0 and 6 is at
index 5, so the distance is 4
Input: arr[] = {2, 5, 3, 5, 4, 4, 2, 3},
x = 3, y = 2
Output: 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 = min(m, j-i)。 -
打印
m的值作为最小距离。
-
-
实现：
C++
```
// C++ program to Find the minimum // distance between two numbers
include
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); } } } 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
include // for abs()
include // for INT_MAX
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); } } } 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 = 3; int y = 6;
printf("Minimum distance between %d and %d is %d\n", 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); } } 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 = 3; 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); } } } return $min_dist; }
// Driver Code $arr = array(3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3); $n = count($arr); $x = 3; $y = 6;
echo "Minimum distance between ",$x, " and ",$y," is "; echo minDist($arr, $n, $x, $y);
// This code is contributed by anuj_67. ?>
```
输出：
Minimum distance between 3 and 6 is 4 -
复杂度分析：
-
时间复杂度：
O(n ^ 2)，嵌套循环用于遍历数组。 -
空间复杂度：
O(1)，不需要额外的空间。
-
方法 2：
-
方法：因此，基本方法是仅检查
x和y的连续对。 对于每个元素x或y，检查先前出现的x或y的索引，如果先前出现的元素与当前元素不相似，则更新最小距离。 但是出现一个问题，如果一个x前面有另一个x并且在y前面有一个y，那么如何获得线对之间的最小距离呢？ 通过仔细分析，可以看到每个x后面紧跟着y，反之亦然，只能是最接近的对（最小距离），因此忽略所有其他对。 -
算法：
-
创建变量
prev = -1和m = INT_MAX。 -
从头到尾遍历整个数组。
-
如果当前元素是
x或y，则prev不等于 -1 并且array[prev]不等于当前元素，则更新m = max(current_index – prev, m)，即找到连续对之间的距离并用它更新m。 -
打印
m的值。
-
-
感谢 wgpshashank 提出了这种方法。
![]()
实现：
C++
```
// C++ implementation of above approach
include
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 previos 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
include // 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 previos 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\n", 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 previos 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\n"%( 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 previos 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. ?>
```
输出：
Minimum distance between 3 and 6 is 1 -
复杂度分析：
-
时间复杂度：
O(n)。仅需要遍历数组一次。
-
空间复杂度：
O(1)。由于不需要额外的空间。
-
如果您发现上述代码/算法有误，请写评论，或者找到其他解决相同问题的方法。
版权属于：月萌API www.moonapi.com，转载请注明出处
