Рубрики

Найти триплет из трех связанных списков с суммой, равной заданному числу

Учитывая три связанных списка, скажем, a, b и c, найдите один узел из каждого списка так, чтобы сумма значений узлов была равна данному числу.
Например, если три связанных списка имеют значения 12-> 6-> 29, 23-> 5-> 8 и 90-> 20-> 59, а заданное число равно 101, выходное значение должно быть равно «6 5 90» ,

В следующих решениях размер всех трех связанных списков предполагается одинаковым для простоты анализа. Следующие решения работают и для связанных списков разных размеров.

Простой способ решить эту проблему — запустить три вложенных цикла. Самый внешний цикл выбирает элемент из списка a, средний цикл выбирает элемент из b, а самый внутренний цикл выбирает из c. Самый внутренний цикл также проверяет, равна ли сумма значений текущих узлов a, b и c данному числу. Временная сложность этого метода будет O (n ^ 3).

Сортировка может использоваться для уменьшения сложности времени до O (n * n). Ниже приведены подробные шаги.
1) Сортировать список b в порядке возрастания и список c в порядке убывания.
2) После сортировки b и c, один за другим выберите элемент из списка a и найдите пару, пройдя по b и c. Смотрите isSumSorted () в следующем коде. Идея аналогична квадратичному алгоритму задачи 3 сумм .

Следующий код реализует только шаг 2. Решение можно легко изменить для несортированных списков, добавив код сортировки слиянием, который обсуждается здесь .

C ++

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

using namespace std;

  
/ * Узел списка ссылок * /

class Node 

    public:

    int data; 

    Node* next; 

}; 

  
/ * Полезная функция для вставки
узел в начале
связанный список * /

void push (Node** head_ref, int new_data) 

    / * выделить узел * /

    Node* new_node = new Node();

  

    / * вставить данные * /

    new_node->data = new_data; 

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref); 

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node; 

  
/ * Функция для проверки наличия трех элементов в a, b
и c, чья сумма равна данному номеру. Функция
предполагает, что список b отсортирован в порядке возрастания
и с сортируется в порядке убывания. * /

bool isSumSorted(Node *headA, Node *headB, 

                Node *headC, int givenNumber) 

    Node *a = headA; 

  

    // Пройдите через все узлы

    while (a != NULL) 

    

        Node *b = headB; 

        Node *c = headC; 

  

        // Для каждого узла списка a укол двух узлов

        // из списков b abd c

        while (b != NULL && c != NULL) 

        

            // Если это триплет с заданной суммой, выведите

            // это и вернуть true

            int sum = a->data + b->data + c->data; 

            if (sum == givenNumber) 

            

            cout << "Triplet Found: " << a->data << " " << 

                                b->data << " " << c->data; 

            return true

            

  

            // Если сумма этого триплета меньше, ищите

            // большие значения в b

            else if (sum < givenNumber) 

                b = b->next; 

            else // Если сумма больше, ищите меньшие значения в c

                c = c->next; 

        

        a = a->next; // Продвигаемся в списке

    

  

    cout << "No such triplet"

    return false

  

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

int main() 

    / * Начнем с пустого списка * /

    Node* headA = NULL; 

    Node* headB = NULL; 

    Node* headC = NULL; 

  

    / * создать связанный список 'a' 10-> 15-> 5-> 20 * /

    push (&headA, 20); 

    push (&headA, 4); 

    push (&headA, 15); 

    push (&headA, 10); 

  

    / * создать отсортированный связанный список 'b' 2-> 4-> 9-> 10 * /

    push (&headB, 10); 

    push (&headB, 9); 

    push (&headB, 4); 

    push (&headB, 2); 

  

    / * создать другой отсортированный

    связанный список 'c' 8-> 4-> 2-> 1 * /

    push (&headC, 1); 

    push (&headC, 2); 

    push (&headC, 4); 

    push (&headC, 8); 

  

    int givenNumber = 25; 

  

    isSumSorted (headA, headB, headC, givenNumber); 

  

    return 0; 

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

С

// C программа для поиска триплета из трех связанных списков с
// сумма равна заданному числу
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

  
/ * Узел списка ссылок * /

struct Node

{

    int data;

    struct Node* next;

};

  
/ * Вспомогательная функция для вставки узла в начале

   связанный список * /

void push (struct Node** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node =

        (struct Node*) malloc(sizeof(struct Node));

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node;

}

  
/ * Функция для проверки, если в a, b есть три элемента

   и c, чья сумма равна данному номеру. Функция

   предполагает, что список b отсортирован в порядке возрастания

   и с сортируется в порядке убывания. * /

bool isSumSorted(struct Node *headA, struct Node *headB, 

                 struct Node *headC, int givenNumber)

{

    struct Node *a = headA;

  

    // Пройдите через все узлы

    while (a != NULL)

    {

        struct Node *b = headB;

        struct Node *c = headC;

  

        // Для каждого узла списка a укол двух узлов

        // из списков b abd c

        while (b != NULL && c != NULL)

        {

            // Если это триплет с заданной суммой, выведите

            // это и вернуть true

            int sum = a->data + b->data + c->data;

            if (sum == givenNumber)

            {

               printf ("Triplet Found: %d %d %d ", a->data,

                                         b->data, c->data);

               return true;

            }

  

            // Если сумма этого триплета меньше, ищите

            // большие значения в b

            else if (sum < givenNumber)

                b = b->next;

            else // Если сумма больше, ищите меньшие значения в c

                c = c->next;

        }

        a = a->next;  // Продвигаемся в списке

    }

  

    printf ("No such triplet");

    return false;

}

  

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

int main()

{

    / * Начнем с пустого списка * /

    struct Node* headA = NULL;

    struct Node* headB = NULL;

    struct Node* headC = NULL;

  

    / * создать связанный список 'a' 10-> 15-> 5-> 20 * /

    push (&headA, 20);

    push (&headA, 4);

    push (&headA, 15);

    push (&headA, 10);

  

    / * создать отсортированный связанный список 'b' 2-> 4-> 9-> 10 * /

    push (&headB, 10);

    push (&headB, 9);

    push (&headB, 4);

    push (&headB, 2);

  

    / * создать другой отсортированный связанный список 'c' 8-> 4-> 2-> 1 * /

    push (&headC, 1);

    push (&headC, 2);

    push (&headC, 4);

    push (&headC, 8);

  

    int givenNumber = 25;

  

    isSumSorted (headA, headB, headC, givenNumber);

  

    return 0;

}

Джава

// Java-программа для поиска триплета из трех связанных списков с
// сумма равна заданному числу

class LinkedList

{

    Node head;  // заголовок списка

  

    / * Узел связанного списка * /

    class Node

    {

        int data;

        Node next;

        Node(int d) {data = d; next = null; }

    }

  

    / * Функция для проверки, если в a, b есть три элемента

      и c, чья сумма равна данному номеру. Функция

      предполагает, что список b отсортирован в порядке возрастания и

      с сортируется в порядке убывания. * /

   boolean isSumSorted(LinkedList la, LinkedList lb, LinkedList lc,

                       int givenNumber)

   {

      Node a = la.head;

  

      // Обходим все узлы ла

      while (a != null)

      {

          Node b = lb.head;

          Node c = lc.head;

  

          // для каждого узла в la выбираем 2 узла из lb и lc

          while (b != null && c!=null)

          {

              int sum = a.data + b.data + c.data;

              if (sum == givenNumber)

              {

                 System.out.println("Triplet found " + a.data +

                                     " " + b.data + " " + c.data);

                 return true;

              }

  

              // Если сумма меньше, ищите большее значение b

              else if (sum < givenNumber)

                b = b.next;

  

              else

                c = c.next;

          }

          a = a.next;

      }

      System.out.println("No Triplet found");

      return false;

   }

  

  

    / * Дана ссылка (указатель на указатель) на голову

       списка и int, нажмите новый узел на передней панели

       из списка. * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

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

    public static void main(String args[])

    {

        LinkedList llist1 = new LinkedList();

        LinkedList llist2 = new LinkedList();

        LinkedList llist3 = new LinkedList();

  

        / * Создать связанный список llist1 100-> 15-> 5-> 20 * /

        llist1.push(20);

        llist1.push(5);

        llist1.push(15);

        llist1.push(100);

  

        / * создать отсортированный связанный список 'b' 2-> 4-> 9-> 10 * /

        llist2.push(10);

        llist2.push(9);

        llist2.push(4);

        llist2.push(2);

  

        / * создать другой отсортированный связанный список 'c' 8-> 4-> 2-> 1 * /

        llist3.push(1);

        llist3.push(2);

        llist3.push(4);

        llist3.push(8);

  

        int givenNumber = 25;

        llist1.isSumSorted(llist1,llist2,llist3,givenNumber);

    }

} / * Этот код предоставлен Раджатом Мишрой * /

C #

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

using System;

  

public class LinkedList

{

    public Node head; // заголовок списка

  

    / * Узел связанного списка * /

    public class Node

    {

        public int data;

        public Node next;

        public Node(int d) 

        {

            data = d; next = null;

        }

    }

  

    / * Функция для проверки, если есть

    три элемента в а, б

    и с, чья сумма равна

    givenNumber. Функция

    предполагает, что список b

    отсортировано в порядке возрастания и

    с сортируется в порядке убывания. * /

bool isSumSorted(LinkedList la, LinkedList lb, 

                LinkedList lc, int givenNumber)

{

    Node a = la.head;

  

    // Обходим все узлы ла

    while (a != null)

    {

        Node b = lb.head;

        Node c = lc.head;

  

        // для каждого узла в la pick

        // 2 узла из lb и lc

        while (b != null && c!=null)

        {

            int sum = a.data + b.data + c.data;

            if (sum == givenNumber)

            {

                Console.WriteLine("Triplet found " + a.data +

                                    " " + b.data + " " + c.data);

                return true;

            }

  

            // Если сумма меньше, то

            // ищем большее значение b

            else if (sum < givenNumber)

                b = b.next;

  

            else

                c = c.next;

        }

        a = a.next;

    }

    Console.WriteLine("No Triplet found");

    return false;

}

  

  

    / * Дана ссылка (указатель на указатель) на голову

    списка и int, нажмите новый узел на передней панели

    из списка. * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

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

    public static void Main(String []args)

    {

        LinkedList llist1 = new LinkedList();

        LinkedList llist2 = new LinkedList();

        LinkedList llist3 = new LinkedList();

  

        / * Создать связанный список llist1 100-> 15-> 5-> 20 * /

        llist1.push(20);

        llist1.push(5);

        llist1.push(15);

        llist1.push(100);

  

        / * создать отсортированный связанный список 'b' 2-> 4-> 9-> 10 * /

        llist2.push(10);

        llist2.push(9);

        llist2.push(4);

        llist2.push(2);

  

        / * создать другой отсортированный связанный список 'c' 8-> 4-> 2-> 1 * /

        llist3.push(1);

        llist3.push(2);

        llist3.push(4);

        llist3.push(8);

  

        int givenNumber = 25;

        llist1.isSumSorted(llist1,llist2,llist3,givenNumber);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

Triplet Found: 15 2 8

Сложность по времени: связанные списки b и c могут быть отсортированы за время O (nLogn) с помощью сортировки слиянием (см. Это ). Шаг 2 занимает O (n * n) времени. Таким образом, общая временная сложность составляет O (nlogn) + O (nlogn) + O (n * n) = O (n * n).

При таком подходе связанные списки b и c сортируются первыми, поэтому их первоначальный порядок будет потерян. Если мы хотим сохранить исходный порядок b и c, мы можем создать копию b и c.

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

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

Найти триплет из трех связанных списков с суммой, равной заданному числу

0.00 (0%) 0 votes