dsal 找到两个数字之间的最小距离

找到两个数字之间的最小距离

原文： 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）并在它们之间采用最小距离的内循环。
算法：
1. 创建一个变量m = INT_MAX。
2. 运行一个嵌套循环，外循环从头到尾运行（循环计数器i），内循环从i + 1到结束运行（循环计数器j）。
3. 如果第i个元素是x，第j个元素是y，反之亦然，则将m更新为m = min(m, j-i)。
4. 打印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，反之亦然，只能是最接近的对（最小距离），因此忽略所有其他对。
算法：
1. 创建变量prev = -1和m = INT_MAX。
2. 从头到尾遍历整个数组。
3. 如果当前元素是x或y，则prev不等于 -1 并且array[prev]不等于当前元素，则更新m = max(current_index – prev, m)，即找到连续对之间的距离并用它更新m。
4. 打印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，转载请注明出处

本文链接：https://www.moonapi.com/news/34403.html

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-24》

分类

最近更新

dsal 找到两个数字之间的最小距离

找到两个数字之间的最小距离

C++

include

C

include

include // for abs()

include // for INT_MAX

Java

Python3

Python3 code to Find the minimum

distance between two numbers

Driver code

This code is contributed by "Abhishek Sharma 44"

C#

PHP

C++

include

C

include

include // For INT_MAX

Java

Python3

Driver program to test above function */

This code is contributed by Shreyanshi Arun.

C#

PHP

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-24》

dsal 找到两个数字之间的最小距离

找到两个数字之间的最小距离

C++

include

C

include

include // for abs()

include // for INT_MAX

Java

Python3

Python3 code to Find the minimum

distance between two numbers

Driver code

This code is contributed by "Abhishek Sharma 44"

C#

PHP

C++

include

C

include

include // For INT_MAX

Java

Python3

Driver program to test above function */

This code is contributed by Shreyanshi Arun.

C#

PHP

留言

联系客服

dsal 查看更多书籍