Рубрики

Найдите минимальное расстояние между двумя числами

Учитывая несортированный массив arr [] и два числа x и y, найдите минимальное расстояние между x и y в arr []. Массив также может содержать дубликаты. Вы можете предположить, что x и y различны и присутствуют в arr [].

Примеры:
Ввод: arr [] = {1, 2}, x = 1, y = 2
Выход: минимальное расстояние между 1 и 2 равно 1.

Ввод: arr [] = {3, 4, 5}, x = 3, y = 5
Выход: минимальное расстояние между 3 и 5 равно 2.

Ввод: arr [] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}, x = 3, y = 6
Выход: минимальное расстояние между 3 и 6 равно 4.

Ввод: arr [] = {2, 5, 3, 5, 4, 4, 2, 3}, x = 3, y = 2
Выход: минимальное расстояние между 3 и 2 равно 1.

Способ 1 (простой)
Используйте два цикла: внешний цикл выбирает все элементы arr [] один за другим. Внутренний цикл выбирает все элементы после элемента, выбранного внешним циклом. Если элементы, выбранные внешним и внутренним циклами, имеют те же значения, что и x или y, то при необходимости обновите минимальное расстояние, рассчитанное до сих пор.

C ++

// C ++ программа для поиска минимума
// расстояние между двумя числами
#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);

            }

        }

    }

    return min_dist;

}

  
/ * Код водителя * /

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;

}

  
// Этот код предоставлен Shivi_Aggarwal

С

// C программа для поиска минимума
// расстояние между двумя числами
#include <stdio.h>
#include <stdlib.h> // for abs()
#include <limits.h> // 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;

}

  
/ * Программа драйвера для тестирования выше функции * /

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-программа для поиска минимума
// расстояние между двумя числами

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 код для поиска минимума
# расстояние между двумя числами

  

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

  

  
# Код драйвера

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))

  
# Этот код предоставлен "Abhishek Sharma 44"

C #

// C # код для поиска минимума
// расстояние между двумя числами

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;

    }

      

    // Функция драйвера

    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));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для поиска минимума
// расстояние между двумя числами

  

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;

}

  

    // Код драйвера

    $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);

  
// Этот код предоставлен anuj_67.
?>


Выход:

Minimum distance between 3 and 6 is 4

Сложность времени: O (n ^ 2)

Метод 2 (хитрый)
1) Пройдите через массив слева и остановитесь, если найдены x или y . Сохранить индекс этого первого вхождения в переменной скажем prev
2) Теперь пройдем arr [] после индекса prev . Если элемент с текущим индексом i совпадает с x или y, то проверьте, отличается ли он от arr [prev] . Если он отличается, обновите минимальное расстояние, если необходимо. Если это то же самое, то обновите prev, то есть, сделайте prev = i .

Спасибо wgpshashank за предложенный подход.

C ++

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  

int minDist(int arr[], int n, int x, int y)

{

    int i = 0;

    int min_dist = INT_MAX;

    int prev;

  

    // Находим первое вхождение

    // любое из двух чисел (х или у)

    // и сохраняем индекс этого

    // вхождение в пред

    for (i = 0; i < n; i++)

    {

        if (arr[i] == x || arr[i] == y)

        {

        prev = i;

        break;

        }

    }

  

    // Траверс после первого вхождения

    for ( ; i < n; i++)

    {

        if (arr[i] == x || arr[i] == y)

        {

            // Если текущий элемент соответствует

            // с любым из двух, затем проверьте

            // если текущий элемент и предыдущий

            // элементы разные Также проверяем

            // если это значение меньше чем

            // минимальное расстояние до сих пор

            if ( arr[prev] != arr[i] &&

                (i - prev) < min_dist )

            {

                min_dist = i - prev;

                prev = i;

            }

            else

                prev = i;

        }

    }

  

    return min_dist;

}

  
/ * Код водителя * /

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;

}

  
// Этот код предоставлен Мукулом Сингхом.

С

#include <stdio.h>
#include <limits.h>  // For INT_MAX

  

int minDist(int arr[], int n, int x, int y)

{

   int i = 0;

   int min_dist = INT_MAX;

   int prev;

  

   // Находим первое вхождение любого из двух чисел (x или y)

   // и сохраняем индекс этого события в prev

   for (i = 0; i < n; i++)

   {

     if (arr[i] == x || arr[i] == y)

     {

       prev = i;

       break;

     }

   }

  

   // Траверс после первого вхождения

   for ( ; i < n; i++)

   {

      if (arr[i] == x || arr[i] == y)

      {

          // Если текущий элемент совпадает с любым из двух, то

          // проверяем, отличаются ли текущий элемент и элемент prev

          // Также проверяем, меньше ли это значение, чем минимальное расстояние

          if ( arr[prev] != arr[i] && (i - prev) < min_dist )

          {

             min_dist = i - prev;

             prev = i;

          }

          else

             prev = i;

      }

   }

  

   return min_dist;

}

  
/ * Программа драйвера для тестирования выше функции * /

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;

}

Джава

class MinimumDistance

{

    int minDist(int arr[], int n, int x, int y) 

    {

        int i = 0;

        int min_dist = Integer.MAX_VALUE;

        int prev=0;

  

        // Находим первое вхождение любого из двух чисел (x или y)

        // и сохраняем индекс этого события в prev

        for (i = 0; i < n; i++) 

        {

            if (arr[i] == x || arr[i] == y) 

            {

                prev = i;

                break;

            }

        }

  

        // Траверс после первого вхождения

        for (; i < n; i++) 

        {

            if (arr[i] == x || arr[i] == y) 

            {

                // Если текущий элемент совпадает с любым из двух, то

                // проверяем, отличаются ли текущий элемент и элемент prev

                // Также проверяем, меньше ли это значение, чем минимальное расстояние

                // слишком далеко

                if (arr[prev] != arr[i] && (i - prev) < min_dist) 

                {

                    min_dist = i - prev;

                    prev = i;

                

                else

                    prev = i;

            }

        }

  

        return min_dist;

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    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):

    min_dist = sys.maxsize

  

    # Найти первое вхождение любого из двух чисел (х или у)

    # и сохранить индекс этого события в пред.

    for i in range(n):

          

        if arr[i] == x or arr[i] == y:

            prev = i

            break

   

    # Траверс после первого появления

    while i < n:

        if arr[i] == x or arr[i] == y:

  

            # Если текущий элемент совпадает с любым из двух, то

            # проверить, отличаются ли текущий элемент и предыдущий элемент

            # Также проверьте, если это значение меньше минимального расстояния до сих пор

            if arr[prev] != arr[i] and (i - prev) < min_dist :

                min_dist = i - prev

                prev = i

            else:

                prev = i

        i += 1        

   

    return min_dist

   
# Программа драйвера для тестирования выше функции * /

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)));

  
# Этот код предоставлен Shreyanshi Arun.

C #

// C # программа для поиска минимума
// расстояние между двумя числами

using System;

class MinimumDistance {

      

    static int minDist(int []arr, int n,

                       int x, int y) 

    {

        int i = 0;

        int min_dist = int.MaxValue;

        int prev=0;

  

        // Находим первый случай любого

        // из двух чисел (х или у)

        // и сохраняем индекс этого

        // вхождение в пред

        for (i = 0; i < n; i++) 

        {

            if (arr[i] == x || arr[i] == y) 

            {

                prev = i;

                break;

            }

        }

  

        // Траверс после

        // первый случай

        for (; i < n; i++) 

        {

            if (arr[i] == x || arr[i] == y) 

            {

                // Если текущий элемент соответствует

                // с любым из двух тогда

                // проверяем текущий элемент и

                // предыдущий элемент отличается

                // Также проверяем, является ли это значение

                // меньше минимального расстояния

                // слишком далеко

                if (arr[prev] != arr[i] && 

                    (i - prev) < min_dist) 

                {

                    min_dist = i - prev;

                    prev = i;

                

                else

                    prev = i;

            }

        }

  

        return min_dist;

    }

  

    // Код драйвера

    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));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для поиска минимума
// расстояние между двумя числами

  

function minDist($arr, $n, $x, $y)

{

    $i = 0;

    $min_dist = PHP_INT_MAX;

    $prev;

      

    // Находим первый случай любого

    // из двух чисел (х или у) и

    // сохраняем индекс этого события

    // в пред

    for ($i = 0; $i < $n; $i++)

    {

        if ($arr[$i] == $x or $arr[$i] == $y)

        {

            $prev = $i;

            break;

        }

    }

      

    // Траверс после первого вхождения

    for ( ; $i < $n; $i++)

    {

        if ($arr[$i] == $x or $arr[$i] == $y)

        {

            // Если текущий элемент соответствует

            // с любым из двух, затем проверьте

            // если текущий элемент и предыдущий

            // элементы разные Также проверяем

            // если это значение меньше чем

            // минимальное расстояние до сих пор

            if ( $arr[$prev] != $arr[$i] and 

                    ($i - $prev) < $min_dist )

            {

                $min_dist = $i - $prev;

                $prev = $i;

            }

            else

                $prev = $i;

        }

    }

      

    return $min_dist;

}

  
/ * Программа драйвера для тестирования выше функции * /

    $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);

  
// Этот код предоставлен anuj_67.
?>


Выход:

Minimum distance between 3 and 6 is 1

Сложность времени: O (n)

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Найдите минимальное расстояние между двумя числами

0.00 (0%) 0 votes