Рубрики

Найти минимальную разницу между любыми двумя элементами

Учитывая несортированный массив, найдите минимальную разницу между любой парой в данном массиве.

Примеры :

Input  : {1, 5, 3, 19, 18, 25};
Output : 1
Minimum difference is between 18 and 19

Input  : {30, 5, 20, 9};
Output : 4
Minimum difference is between 5 and 9

Input  : {1, 19, -4, 31, 38, 25, 100};
Output : 5
Minimum difference is between 1 and -4

Метод 1 (Простой: O (n 2 )
Простое решение — использовать две петли.

C / C ++

// C ++ реализация простого метода для поиска
// минимальная разница между любой парой
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает минимальную разницу между любой парой

int findMinDiff(int arr[], int n)

{

   // Инициализируем разницу как бесконечную

   int diff = INT_MAX;

  

   // Находим минимальную разницу, сравнивая разницу

   // всех возможных пар в данном массиве

   for (int i=0; i<n-1; i++)

      for (int j=i+1; j<n; j++)

          if (abs(arr[i] - arr[j]) < diff)

                diff = abs(arr[i] - arr[j]);

  

   // Возвращаем min diff

   return diff;

}

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

int main()

{

   int arr[] = {1, 5, 3, 19, 18, 25};

   int n = sizeof(arr)/sizeof(arr[0]);

   cout << "Minimum difference is " << findMinDiff(arr, n);

   return 0;

}

Джава

// Java реализация простого метода для поиска
// минимальная разница между любой парой

  

class GFG

{

    // Возвращает минимальную разницу между любой парой

    static int findMinDiff(int[] arr, int n)

    {

        // Инициализируем разницу как бесконечную

        int diff = Integer.MAX_VALUE;

      

        // Находим минимальную разницу, сравнивая разницу

        // всех возможных пар в данном массиве

        for (int i=0; i<n-1; i++)

            for (int j=i+1; j<n; j++)

                if (Math.abs((arr[i] - arr[j]) )< diff)

                    diff = Math.abs((arr[i] - arr[j]));

      

        // Возвращаем min diff

        return diff;

    }

  

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args)

    {

        int arr[] = new int[]{1, 5, 3, 19, 18, 25};

        System.out.println("Minimum difference is "+

                              findMinDiff(arr, arr.length));

      

    }

}

питон

# Python реализация простого метода для поиска
# минимальная разница между любой парой

  
# Возвращает минимальную разницу между любой парой

def findMinDiff(arr, n):

    # Инициализировать разницу как бесконечную

    diff = 10**20

      

    # Найти минимальный дифференциал, сравнивая разницу

    # всех возможных пар в данном массиве

    for i in range(n-1):

        for j in range(i+1,n):

            if abs(arr[i]-arr[j]) < diff:

                diff = abs(arr[i] - arr[j])

  

    # Возврат min diff

    return diff

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

arr = [1, 5, 3, 19, 18, 25]

n = len(arr)

print("Minimum difference is " + str(findMinDiff(arr, n)))

  
# Этот код предоставлен Pratik Chhajer

C #

// C # реализация простого метода для поиска
// минимальная разница между любой парой

using System;

  

class GFG {

      

    // Возвращает минимальную разницу между любой парой

    static int findMinDiff(int []arr, int n)

    {

          

        // Инициализируем разницу как бесконечную

        int diff = int.MaxValue;

      

        // Находим минимальную разницу, сравнивая разницу

        // всех возможных пар в данном массиве

        for (int i = 0; i < n-1; i++)

            for (int j = i+1; j < n; j++)

                if (Math.Abs((arr[i] - arr[j]) ) < diff)

                    diff = Math.Abs((arr[i] - arr[j]));

      

        // Возвращаем min diff

        return diff;

    }

  

    // Метод драйвера для проверки вышеуказанной функции

    public static void Main()

    {

        int []arr = new int[]{1, 5, 3, 19, 18, 25};

        Console.Write("Minimum difference is " +

                        findMinDiff(arr, arr.Length));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// простая реализация PHP
// метод поиска минимума
// разница между любой парой

  
// Возвращает минимальную разницу
// между любой парой

function findMinDiff($arr, $n)

{
// Инициализируем разницу
// как бесконечный

$diff = PHP_INT_MAX;

  
// Найти минимальный дифференциал путем сравнения
// разница всего возможного
// пары в заданном массиве

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

    for ($j = $i + 1; $j < $n; $j++)

        if (abs($arr[$i] - $arr[$j]) < $diff)

                $diff = abs($arr[$i] - $arr[$j]);

  
// Возвращаем min diff

return $diff;

}

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

$arr = array(1, 5, 3, 19, 18, 25);

$n = sizeof($arr);

echo "Minimum difference is " ,

         findMinDiff($arr, $n);

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


Выход :

Minimum difference is 1

Метод 2 (Эффективный: O (n Log n)
Идея состоит в том, чтобы использовать сортировку. Ниже приведены шаги.
1) Сортировать массив в порядке возрастания. Этот шаг занимает O (n Log n) времени.
2) Инициализируйте разницу как бесконечную. Этот шаг занимает O (1) раз.
3) Сравнить все соседние пары в отсортированном массиве и отслеживать минимальную разницу. Этот шаг занимает O (N) времени.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска минимальной разницы между
// любая пара в несортированном массиве
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает минимальную разницу между любой парой

int findMinDiff(int arr[], int n)

{

   // Сортировать массив в порядке убывания

   sort(arr, arr+n);

  

   // Инициализируем разницу как бесконечную

   int diff = INT_MAX;

  

   // Находим минимальный дифференциал, сравнивая соседние

   // пары в отсортированном массиве

   for (int i=0; i<n-1; i++)

      if (arr[i+1] - arr[i] < diff)

          diff = arr[i+1] - arr[i];

  

   // Возвращаем min diff

   return diff;

}

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

int main()

{

   int arr[] = {1, 5, 3, 19, 18, 25};

   int n = sizeof(arr)/sizeof(arr[0]);

   cout << "Minimum difference is " << findMinDiff(arr, n);

   return 0;

}

Джава

// Java программа для поиска минимальной разницы между
// любая пара в несортированном массиве

  

import java.util.Arrays;

  

class GFG

{

    // Возвращает минимальную разницу между любой парой

    static int findMinDiff(int[] arr, int n)

    {

           // Сортировать массив в порядке убывания

           Arrays.sort(arr);

           

           // Инициализируем разницу как бесконечную

           int diff = Integer.MAX_VALUE;

           

           // Находим минимальный дифференциал, сравнивая соседние

           // пары в отсортированном массиве

           for (int i=0; i<n-1; i++)

              if (arr[i+1] - arr[i] < diff)

                  diff = arr[i+1] - arr[i];

           

           // Возвращаем min diff

           return diff;

    }

  

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args)

    {

        int arr[] = new int[]{1, 5, 3, 19, 18, 25};

        System.out.println("Minimum difference is "+

                              findMinDiff(arr, arr.length));

      

    }

}

питон

# Программа Python, чтобы найти минимальную разницу между
# любая пара в несортированном массиве

  
# Возвращает минимальную разницу между любой парой

def findMinDiff(arr, n):

  

    # Сортировать массив в порядке убывания

    arr = sorted(arr)

  

    # Инициализировать разницу как бесконечную

    diff = 10**20

  

    # Найти минимальный дифференциал, сравнивая соседние

    # пар в отсортированном массиве

    for i in range(n-1):

        if arr[i+1] - arr[i] < diff:

            diff = arr[i+1] - arr[i]

  

    # Возврат min diff

    return diff

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

arr = [1, 5, 3, 19, 18, 25]

n = len(arr)

print("Minimum difference is " + str(findMinDiff(arr, n)))

  
# Этот код предоставлен Pratik Chhajer

C #

// C # программа для поиска минимума
// разница между любой парой
// в несортированном массиве

using System;

  

class GFG

{

    // Возвращает минимальную разницу

    // между любой парой

    static int findMinDiff(int[] arr, 

                           int n)

    {

        // Сортировать массив в

        // неубывающий порядок

        Array.Sort(arr);

          

        // Инициализируем разницу

        // как бесконечный

        int diff = int.MaxValue;

          

        // Найти минимальный дифференциал по

        // сравниваем соседние пары

        // в отсортированном массиве

        for (int i = 0; i < n - 1; i++)

            if (arr[i + 1] - arr[i] < diff)

                diff = arr[i + 1] - arr[i];

          

        // Возвращаем min diff

        return diff;

    }

  

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

    public static void Main()

    {

        int []arr = new int[]{1, 5, 3, 19, 18, 25};

        Console.WriteLine("Minimum difference is " +

                           findMinDiff(arr, arr.Length));

      

    }

}

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

PHP

<?php
// PHP программа для поиска минимума
// разница между любой парой
// в несортированном массиве

  
// Возвращает минимальную разницу
// между любой парой

function findMinDiff($arr, $n)

{

      
// Сортировать массив в
// неубывающий порядок

sort($arr);

  
// Инициализируем разницу
// как бесконечный

$diff = PHP_INT_MAX;

  
// Найти минимальный дифференциал по
// сравнение соседних
// пары в отсортированном массиве

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

    if ($arr[$i + 1] - $arr[$i] < $diff)

        $diff = $arr[$i + 1] - $arr[$i];

  
// Возвращаем min diff

return $diff;

}

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

$arr = array(1, 5, 3, 19, 18, 25);

$n = sizeof($arr);

echo "Minimum difference is "

         findMinDiff($arr, $n);

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


Выход :

Minimum difference is 1

Спросил в: Amazon

Эта статья предоставлена Харшитом Агравалом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Найти минимальную разницу между любыми двумя элементами

0.00 (0%) 0 votes