Рубрики

Проблема с гайками и болтами (проблема с замком и ключом) | Комплект 1

Дан набор из n гаек разных размеров и n болтов разных размеров. Существует взаимно-однозначное соответствие между гайками и болтами. Эффективно сочетайте гайки и болты.
Ограничение: Сравнение гайки с другой гайкой или болта с другим болтом не допускается. Это означает, что гайку можно сравнить только с болтом, а болт можно сравнить только с гайкой, чтобы увидеть, какая из них больше / меньше.

Другой способ задать эту проблему — получить коробку с замками и ключами, где один замок можно открыть одним ключом в коробке. Нам нужно сопоставить пару.

Путь грубой силы: начните с первого болта и сравнивайте его с каждой гайкой, пока не найдете совпадение. В худшем случае нам нужно n сравнений. Выполнение этого для всех болтов дает нам сложность O (n ^ 2).

Быстрая сортировка: мы можем использовать метод быстрой сортировки, чтобы решить эту проблему. Мы представляем гайки и болты в массиве символов для понимания логики.

Орехи представлены в виде массива символов
char nuts [] = {'@', '#', '$', '%', '^', '&'}

Болты представлены в виде массива символов
char bolts [] = {'$', '%', '&', '^', '@', '#'}

Этот алгоритм сначала выполняет разбиение, выбирая последний элемент массива болтов как шарнир, переставляет массив гаек и возвращает индекс разбиения 'i' так, что все гайки, меньшие, чем гайки [i], находятся на левой стороне, а все гайки больше, чем гайки. [Я] на правой стороне. Далее, используя гайки [i], мы можем разбить массив болтов. Операции разбиения могут быть легко реализованы в O (n). Эта операция также делает массив гаек и болтов хорошо разделенным. Теперь мы применим это разбиение рекурсивно к левому и правому массиву гаек и болтов.

Так как мы применяем разбиение на гайки и болты, общая сложность времени в среднем составит Θ (2 * nlogn) = Θ (nlogn).

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

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

Джава

// Java-программа для решения проблемы с гайками и болтами с помощью быстрой сортировки

public class NutsAndBoltsMatch

{

    // Метод драйвера

    public static void main(String[] args)

    {

        // Гайки и болты представлены в виде массива символов

        char nuts[] = {'@', '#', '$', '%', '^', '&'};

        char bolts[] = {'$', '%', '&', '^', '@', '#'};

  

        // Метод, основанный на быстрой сортировке, который соответствует гайки и болты

        matchPairs(nuts, bolts, 0, 5);

  

        System.out.println("Matched nuts and bolts are : ");

        printArray(nuts);

        printArray(bolts);

    }

  

    // Метод для печати массива

    private static void printArray(char[] arr) {

        for (char ch : arr){

            System.out.print(ch + " ");

        }

        System.out.print("n");

    }

  

    // Метод, который работает так же, как быстрая сортировка

    private static void matchPairs(char[] nuts, char[] bolts, int low,

                                                              int high)

    {

        if (low < high)

        {

            // Выберите последний символ массива болтов для раздела гаек.

            int pivot = partition(nuts, low, high, bolts[high]);

  

            // Теперь с помощью разбиения гаек выбираем, что для болтов

            // раздел.

            partition(bolts, low, high, nuts[pivot]);

  

            // Повторяем для [low ... pivot-1] & [pivot + 1 ... high] для орехов и

            // массив болтов.

            matchPairs(nuts, bolts, low, pivot-1);

            matchPairs(nuts, bolts, pivot+1, high);

        }

    }

  

    // Аналог стандартного метода разбиения. Здесь мы передаем элемент поворота

    // тоже вместо выбора внутри метода.

    private static int partition(char[] arr, int low, int high, char pivot)

    {

        int i = low;

        char temp1, temp2;

        for (int j = low; j < high; j++)

        {

            if (arr[j] < pivot){

                temp1 = arr[i];

                arr[i] = arr[j];

                arr[j] = temp1;

                i++;

            } else if(arr[j] == pivot){

                temp1 = arr[j];

                arr[j] = arr[high];

                arr[high] = temp1;

                j--;

            }

        }

        temp2 = arr[i];

        arr[i] = arr[high];

        arr[high] = temp2;

  

        // Возвращаем индекс раздела массива на основе пивота

        // элемент другого массива.

        return i;

    }

}

C #

// C # программа для решения гайки и
// проблема с использованием быстрой сортировки

using System;

using System.Collections.Generic;

      

class GFG 

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

    public static void Main(String[] args) 

    

        // Гайки и болты представлены

        // как массив символов

        char []nuts = {'@', '#', '$', '%', '^', '&'}; 

        char []bolts = {'$', '%', '&', '^', '@', '#'}; 

  

        // Метод, основанный на быстрой сортировке

        // который соответствует гайки и болты

        matchPairs(nuts, bolts, 0, 5); 

  

        Console.WriteLine("Matched nuts and bolts are : "); 

        printArray(nuts); 

        printArray(bolts); 

    

  

    // Метод для печати массива

    private static void printArray(char[] arr) 

    

        foreach (char ch in arr)

        

            Console.Write(ch + " "); 

        

        Console.Write("\n"); 

    

  

    // Метод, который работает так же, как быстрая сортировка

    private static void matchPairs(char[] nuts, 

                                   char[] bolts, 

                                   int low, int high) 

    

        if (low < high) 

        

            // Выберите последний символ

            // массив болтов для раздела гаек.

            int pivot = partition(nuts, low, 

                                  high, bolts[high]); 

  

            // Теперь используем раздел орехов

            // выбираем это для раздела болтов.

            partition(bolts, low, high, nuts[pivot]); 

  

            // Повтор для [low ... pivot-1] &

            // [pivot + 1 ... high] для орехов

            // и массив болтов.

            matchPairs(nuts, bolts, low, pivot - 1); 

            matchPairs(nuts, bolts, pivot + 1, high); 

        

    

  

    // Аналог стандартного метода разбиения.

    // Здесь мы также передаем элемент поворота

    // вместо выбора внутри метода.

    private static int partition(char[] arr, int low,

                                 int high, char pivot) 

    

        int i = low; 

        char temp1, temp2; 

        for (int j = low; j < high; j++) 

        

            if (arr[j] < pivot)

            

                temp1 = arr[i]; 

                arr[i] = arr[j]; 

                arr[j] = temp1; 

                i++; 

            

            else if(arr[j] == pivot)

            

                temp1 = arr[j]; 

                arr[j] = arr[high]; 

                arr[high] = temp1; 

                j--; 

            

        

        temp2 = arr[i]; 

        arr[i] = arr[high]; 

        arr[high] = temp2; 

  

        // Возвращаем индекс раздела массива

        // на основе элемента pivot другого массива.

        return i; 

    

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


Выход:

Matched nuts and bolts are :
# $ % & @ ^
# $ % & @ ^ 

Проблема с гайками и болтами (проблема с замком и ключом) | Набор 2 (Hashmap)

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

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

Проблема с гайками и болтами (проблема с замком и ключом) | Комплект 1

0.00 (0%) 0 votes