Рубрики

Найти три ближайших элемента из заданных трех отсортированных массивов

Учитывая три отсортированных массива A [], B [] и C [], найдите 3 элемента i, j и k из A, B и C соответственно так, чтобы max (abs (A [i] — B [j]), abs ( B [j] — C [k]), abs (C [k] — A [i])) сведено к минимуму. Здесь abs () указывает абсолютное значение.

Пример :

Input: A[] = {1, 4, 10}
       B[] = {2, 15, 20}
       C[] = {10, 12}
Output: 10 15 10
10 from A, 15 from B and 10 from C

Input: A[] = {20, 24, 100}
       B[] = {2, 19, 22, 79, 800}
       C[] = {10, 12, 23, 24, 119}
Output: 24 22 23
24 from A, 22 from B and 23 from C

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Простое решение — запустить три вложенных цикла, чтобы рассмотреть все триплеты из A, B и C. Вычислить значение max (abs (A [i] — B [j]), abs (B [j] — C [k] ), abs (C [k] — A [i])) для каждого триплета и возвращает минимум всех значений. Временная сложность этого решения составляет O (n 3 )

Лучшее решение для нас — бинарный поиск.
1) перебрать все элементы A [],
a) Двоичный поиск элемента, который меньше или равен в B [] и C [], и обратите внимание на разницу.
2) Повторите шаг 1 для B [] и C [].
3) Возврат общего минимума.

Временная сложность этого решения O (nLogn)

Эффективное решение Пусть 'p' будет размером A [], 'q' будет размером B [] и 'r' будет размером C []

1)   Start with i=0, j=0 and k=0 (Three index variables for A,
                                  B and C respectively)

//  p, q and r are sizes of A[], B[] and C[] respectively.
2)   Do following while i < p and j < q and k < r
    a) Find min and maximum of A[i], B[j] and C[k]
    b) Compute diff = max(X, Y, Z) - min(A[i], B[j], C[k]).
    c) If new result is less than current result, change 
       it to the new result.
    d) Increment the pointer of the array which contains 
       the minimum.

Обратите внимание, что мы увеличиваем указатель массива, который имеет минимум, потому что наша цель — уменьшить разницу. Увеличение максимального указателя увеличивает разницу. Увеличение второго максимального указателя может потенциально увеличить разницу.

C ++

// C ++ программа для поиска 3 элементов, таких что max (abs (A [i] -B [j]), abs (B [j] -
// C [k]), abs (C [k] -A [i])) сведено к минимуму.

  
#include<bits/stdc++.h>

using namespace std;

  

void findClosest(int A[], int B[], int C[], int p, int q, int r)

{

  

    int diff = INT_MAX;  // Инициализируем min diff

  

    // Инициализировать результат

    int res_i =0, res_j = 0, res_k = 0;

  

    // Перемещение массивов

    int i=0,j=0,k=0;

    while (i < p && j < q && k < r)

    {

        // Находим минимум и максимум трех текущих элементов

        int minimum = min(A[i], min(B[j], C[k]));

        int maximum = max(A[i], max(B[j], C[k]));

  

        // Обновить результат, если текущая разница меньше минимальной

        // пока что

        if (maximum-minimum < diff)

        {

             res_i = i, res_j = j, res_k = k;

             diff = maximum - minimum;

        }

  

        // Мы не можем получить меньше 0, поскольку значения абсолютны

        if (diff == 0) break;

  

        // Увеличиваем индекс массива с наименьшим значением

        if (A[i] == minimum) i++;

        else if (B[j] == minimum) j++;

        else k++;

    }

  

    // Распечатать результат

    cout << A[res_i] << " " << B[res_j] << " " << C[res_k];

}

  
// Драйвер программы

int main()

{

    int A[] = {1, 4, 10};

    int B[] = {2, 15, 20};

    int C[] = {10, 12};

  

    int p = sizeof A / sizeof A[0];

    int q = sizeof B / sizeof B[0];

    int r = sizeof C / sizeof C[0];

  

    findClosest(A, B, C, p, q, r);

    return 0;

}

Джава

// Java программа для поиска 3 элементов
// что max (abs (A [i] -B [j]), abs (B [j] -C [k]),
// abs (C [k] -A [i])) сведено к минимуму.

import java.io.*;

  

class GFG {

      

    static void findClosest(int A[], int B[], int C[],

                                  int p, int q, int r)

    {

        int diff = Integer.MAX_VALUE; // Инициализируем min diff

      

        // Инициализировать результат

        int res_i =0, res_j = 0, res_k = 0;

      

        // Перемещение массивов

        int i = 0, j = 0, k = 0;

        while (i < p && j < q && k < r)

        {

            // Находим минимум и максимум трех текущих элементов

            int minimum = Math.min(A[i],

                          Math.min(B[j], C[k]));

            int maximum = Math.max(A[i], 

                          Math.max(B[j], C[k]));

      

            // Обновить результат, если текущая разница

            // меньше, чем минимальная разница

            if (maximum-minimum < diff)

            {

                res_i = i;

                res_j = j;

                res_k = k;

                diff = maximum - minimum;

            }

      

            // Мы не можем получить меньше 0

            // поскольку значения абсолютные

            if (diff == 0) break;

      

            // Инкрементный индекс массива

            // с наименьшим значением

            if (A[i] == minimum) i++;

            else if (B[j] == minimum) j++;

            else k++;

        }

      

        // Распечатать результат

        System.out.println(A[res_i] + " " +

                           B[res_j] + " " + C[res_k]);

    }

  

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

    public static void main (String[] args)

    {

        int A[] = {1, 4, 10};

        int B[] = {2, 15, 20};

        int C[] = {10, 12};

      

        int p = A.length;

        int q = B.length;

        int r = C.length;

      

        // вызов функции

        findClosest(A, B, C, p, q, r);

    }

}

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

python3

# Программа Python, чтобы найти 3 элемента, такие
# что max (абс (A [i] -B [j]), абс (B [j] - C [k]),
# abs (C [k] -A [i])) сведено к минимуму.

import sys

  

def findCloset(A, B, C, p, q, r):

  

    # Инициализировать min diff

    diff = sys.maxsize

  

    res_i = 0

    res_j = 0

    res_k = 0

  

    # Travesre Array

    i = 0

    j = 0

    k = 0

    while(i < p and j < q and k < r):

  

        # Найти минимум и максимум

        # текущие три элемента

        minimum = min(A[i], min(B[j], C[k]))

        maximum = max(A[i], max(B[j], C[k]));

  

        # Обновить результат, если текущая разница

        # меньше, чем минимальная разница до сих пор

        if maximum-minimum < diff:

            res_i = i

            res_j = j

            res_k = k

            diff = maximum - minimum;

  

        # Мы не можем получить меньше 0, как

        # значения являются абсолютными

        if diff == 0:

            break

  

  

        # Увеличить индекс массива с

        # наименьшее значение

        if A[i] == minimum:

            i = i+1

        elif B[j] == minimum:

            j = j+1

        else:

            k = k+1

  

    # Печать результата

    print(A[res_i], " ", B[res_j], " ", C[res_k])

  
# Драйверная программа

A = [1, 4, 10]

B = [2, 15, 20]

C = [10, 12]

  

p = len(A)

q = len(B)

r = len(C)

  
findCloset(A,B,C,p,q,r)

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

C #

// C # программа для поиска 3 элементов
// такой, что max (abs (A [i] -B [j]),
// abs (B [j] -C [k]), abs (C [k] -A [i]))
// свернут

using System;

  

class GFG 

{

    static void findClosest(int []A, int []B, 

                            int []C, int p,

                            int q, int r)

    {

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

        int diff = int.MaxValue; 

      

        // Инициализировать результат

        int res_i = 0, 

            res_j = 0, 

            res_k = 0;

      

        // Перемещение массивов

        int i = 0, j = 0, k = 0;

        while (i < p && j < q && k < r)

        {

            // Находим минимум и максимум

            // текущих трех элементов

            int minimum = Math.Min(A[i],

                          Math.Min(B[j], C[k]));

            int maximum = Math.Max(A[i], 

                          Math.Max(B[j], C[k]));

      

            // Обновить результат, если текущий

            // разница меньше минимальной

            // пока что

            if (maximum - minimum < diff)

            {

                res_i = i;

                res_j = j;

                res_k = k;

                diff = maximum - minimum;

            }

      

            // Мы не можем получить меньше 0

            // поскольку значения абсолютные

            if (diff == 0) break;

      

            // Инкрементный индекс массива

            // с наименьшим значением

            if (A[i] == minimum) i++;

            else if (B[j] == minimum) j++;

            else k++;

        }

      

        // Распечатать результат

        Console.WriteLine(A[res_i] + " " +

                          B[res_j] + " "

                          C[res_k]);

    }

  

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

    public static void Main ()

    {

        int []A = {1, 4, 10};

        int []B = {2, 15, 20};

        int []C = {10, 12};

      

        int p = A.Length;

        int q = B.Length;

        int r = C.Length;

      

        // вызов функции

        findClosest(A, B, C, p, q, r);

    }

}

  
// Этот код добавлен
// от anuj_67.

PHP

<?php
// PHP программа для поиска 3 элементов
// что max (abs (A [i] -B [j]), abs (B [j] -
// C [k]), abs (C [k] -A [i])) сведено к минимуму.

  

function findClosest($A, $B, $C, $p, $q, $r

  

    $diff = PHP_INT_MAX; // Инициализируем min diff

  

    // Инициализировать результат

    $res_i = 0;

    $res_j = 0;

    $res_k = 0; 

  

    // Перемещение массивов

    $i = 0;

    $j = 0;

    $k = 0; 

    while ($i < $p && $j < $q && $k < $r

    

        // Находим минимум и максимум

        // текущие три элемента

        $minimum = min($A[$i], min($B[$j], $C[$k])); 

        $maximum = max($A[$i], max($B[$j], $C[$k])); 

  

        // Обновить результат, если текущая разница

        // меньше, чем минимальная разница

        if ($maximum-$minimum < $diff

        

            $res_i = $i; $res_j = $j; $res_k = $k

            $diff = $maximum - $minimum

        

  

        // Мы не можем получить меньше 0 как

        // значения абсолютные

        if ($diff == 0) break

  

        // Увеличиваем индекс массива с

        // наименьшее значение

        if ($A[$i] == $minimum) $i++; 

        else if ($B[$j] == $minimum) $j++; 

        else $k++; 

    

  

    // Распечатать результат

    echo $A[$res_i] , " ", $B[$res_j], 

                      " ", $C[$res_k]; 

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

$A = array(1, 4, 10); 

$B = array(2, 15, 20); 

$C = array(10, 12); 

  

$p = sizeof($A); 

$q = sizeof($B); 

$r = sizeof($C); 

  

findClosest($A, $B, $C, $p, $q, $r); 

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


Выход:

10 15 10

Временная сложность этого решения составляет O (p + q + r), где p, q и r — размеры A [], B [] и C [] соответственно.

Спасибо Gaurav Ahirwar за предложенные выше решения.

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

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

Найти три ближайших элемента из заданных трех отсортированных массивов

0.00 (0%) 0 votes