K-ésimo elemento más pequeño en un árbol N-ario

Dado un N-array Tree (Árbol genérico) y un número entero K , la tarea es encontrar el K -ésimo elemento más pequeño en un N-array Tree .

Ejemplos:

Entrada:                    10 
                         / / \ \ 
                      2 34 56 100 
                     / \ | / | \ 
                77 88 1 7 8 9 
                    K = 3 
Salida:
Explicación: 7 es el tercer elemento más pequeño del árbol. Los dos primeros elementos más pequeños son 1 y 2 respectivamente.

Entrada:                            1
                                   / \ \
                                 2 3 4
                              / \
                            5 6 
                             K = 4
Salida : 4

Enfoque: el problema se puede resolver encontrando el elemento más pequeño en el rango dado K veces y continuando actualizando el extremo superior del rango al elemento más pequeño encontrado hasta el momento. Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable global, digamos MinimalElement como INT_MAX .
  • Declare una función más pequeña EleUnderRange (raíz, datos) y realice las siguientes operaciones: 
    • Si root.data es más que data , entonces actualice MinimalElement como mínimo de MinimalElement y root.data.
    • Iterar sobre todos los hijos de la raíz . Llame a la función recursiva más pequeñoEleUnderRange (hijo, datos).
  • Declare una función KthSmallestElement(root, k) para realizar las siguientes operaciones:
    • Inicialice una variable, digamos ans como INT_MIN , para almacenar el K -ésimo elemento más pequeño .
    • Iterar sobre el rango [0, K – 1] usando una variable i y realizar lo siguiente:
      • Llame a la función más pequeñoEleUnderRange (root, ans) y luego actualice ans como Elemento Mínimo y luego Elemento Mínimo como INT_MAX .
    • Finalmente, escriba ans como la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a node
class Node {
public:
    int data;
    vector<Node*> childs;
};
 
// Global variable set to Maximum
int MinimumElement = INT_MAX;
 
// Function that gives the smallest
// element under the range of key
void smallestEleUnderRange(Node* root,
                           int data)
{
    if (root->data > data) {
        MinimumElement = min(
            root->data, MinimumElement);
    }
    for (Node* child : root->childs) {
        smallestEleUnderRange(child, data);
    }
}
 
// Function to find the Kth smallest element
int kthSmallestElement(Node* root, int k)
{
    int ans = INT_MIN;
    for (int i = 0; i < k; i++) {
        smallestEleUnderRange(root, ans);
        ans = MinimumElement;
        MinimumElement = INT_MAX;
    }
    return ans;
}
 
// Function to create a new node
Node* newNode(int data)
{
    Node* temp = new Node();
    temp->data = data;
    return temp;
}
 
// Driver Code
int main()
{
    /*   Let us create below tree
     *              10
     *        /   /    \   \
     *        2  34    56   100
     *       / \         |   /  | \
     *      77  88       1   7  8  9
     */
 
    Node* root = newNode(10);
    (root->childs).push_back(newNode(2));
    (root->childs).push_back(newNode(34));
    (root->childs).push_back(newNode(56));
    (root->childs).push_back(newNode(100));
    (root->childs[0]->childs).push_back(newNode(77));
    (root->childs[0]->childs).push_back(newNode(88));
    (root->childs[2]->childs).push_back(newNode(1));
    (root->childs[3]->childs).push_back(newNode(7));
    (root->childs[3]->childs).push_back(newNode(8));
    (root->childs[3]->childs).push_back(newNode(9));
 
    cout << kthSmallestElement(root, 3);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class Main
{
    // Class containing left and
    // right child of current
    // node and key value
    static class Node {
         
        public int data;
        public Vector<Node> childs;
         
        public Node(int data)
        {
            this.data = data;
            childs = new Vector<Node>();
        }
    }
     
    // Global variable set to Maximum
    static int MinimumElement = Integer.MAX_VALUE;
       
    // Function that gives the smallest
    // element under the range of key
    static void smallestEleUnderRange(Node root, int data)
    {
        if (root.data > data) {
            MinimumElement = Math.min(root.data, MinimumElement);
        }
        for(Node child : root.childs) {
            smallestEleUnderRange(child, data);
        }
    }
       
    // Function to find the Kth smallest element
    static int kthSmallestElement(Node root, int k)
    {
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < k; i++) {
            smallestEleUnderRange(root, ans);
            ans = MinimumElement;
            MinimumElement = Integer.MAX_VALUE;
        }
        return ans;
    }
       
    // Function to create a new node
    static Node newNode(int data)
    {
        Node temp = new Node(data);
        return temp;
    }
     
    public static void main(String[] args) {
        /*   Let us create below tree
         *              10
         *        /   /    \   \
         *        2  34    56   100
         *       / \         |   /  | \
         *      77  88       1   7  8  9
         */
        
        Node root = newNode(10);
        (root.childs).add(newNode(2));
        (root.childs).add(newNode(34));
        (root.childs).add(newNode(56));
        (root.childs).add(newNode(100));
        (root.childs.get(0).childs).add(newNode(77));
        (root.childs.get(0).childs).add(newNode(88));
        (root.childs.get(2).childs).add(newNode(1));
        (root.childs.get(3).childs).add(newNode(7));
        (root.childs.get(3).childs).add(newNode(8));
        (root.childs.get(3).childs).add(newNode(9));
        
        System.out.print(kthSmallestElement(root, 3));
    }
}
 
// This code is contributed by mukesh07.

Python3

# Python3 program for the above approach
import sys
 
# Structure of a node
class Node:
    def __init__(self, data):
        self.data = data
        self.childs = []
 
# Global variable set to Maximum
MinimumElement = sys.maxsize
 
# Function that gives the smallest
# element under the range of key
def smallestEleUnderRange(root, data):
    global MinimumElement
    if root.data > data:
        MinimumElement = min(root.data, MinimumElement)
    for child in range(len(root.childs)):
        smallestEleUnderRange(root.childs[child], data)
 
# Function to find the Kth smallest element
def kthSmallestElement(root, k):
    global MinimumElement
    ans = -sys.maxsize
    for i in range(k):
        smallestEleUnderRange(root, ans)
        ans = MinimumElement
        MinimumElement = sys.maxsize
    return ans
 
# Function to create a new node
def newNode(data):
    temp = Node(data)
    return temp
 
"""   Let us create below tree
 *              10
 *        /   /    \   \
 *        2  34    56   100
 *       / \         |   /  | \
 *      77  88       1   7  8  9
"""
 
root = newNode(10)
(root.childs).append(newNode(2))
(root.childs).append(newNode(34))
(root.childs).append(newNode(56))
(root.childs).append(newNode(100))
(root.childs[0].childs).append(newNode(77))
(root.childs[0].childs).append(newNode(88))
(root.childs[2].childs).append(newNode(1))
(root.childs[3].childs).append(newNode(7))
(root.childs[3].childs).append(newNode(8))
(root.childs[3].childs).append(newNode(9))
 
print(kthSmallestElement(root, 3))
 
# This code is contributed by divyesh072019.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Class containing left and
    // right child of current
    // node and key value
    class Node {
        
        public int data;
        public List<Node> childs;
        
        public Node(int data)
        {
            this.data = data;
            childs = new List<Node>();
        }
    }
     
    // Global variable set to Maximum
    static int MinimumElement = Int32.MaxValue;
      
    // Function that gives the smallest
    // element under the range of key
    static void smallestEleUnderRange(Node root, int data)
    {
        if (root.data > data) {
            MinimumElement = Math.Min(root.data, MinimumElement);
        }
        foreach(Node child in root.childs) {
            smallestEleUnderRange(child, data);
        }
    }
      
    // Function to find the Kth smallest element
    static int kthSmallestElement(Node root, int k)
    {
        int ans = Int32.MinValue;
        for (int i = 0; i < k; i++) {
            smallestEleUnderRange(root, ans);
            ans = MinimumElement;
            MinimumElement = Int32.MaxValue;
        }
        return ans;
    }
      
    // Function to create a new node
    static Node newNode(int data)
    {
        Node temp = new Node(data);
        return temp;
    }
     
  static void Main() {
    /*   Let us create below tree
     *              10
     *        /   /    \   \
     *        2  34    56   100
     *       / \         |   /  | \
     *      77  88       1   7  8  9
     */
   
    Node root = newNode(10);
    (root.childs).Add(newNode(2));
    (root.childs).Add(newNode(34));
    (root.childs).Add(newNode(56));
    (root.childs).Add(newNode(100));
    (root.childs[0].childs).Add(newNode(77));
    (root.childs[0].childs).Add(newNode(88));
    (root.childs[2].childs).Add(newNode(1));
    (root.childs[3].childs).Add(newNode(7));
    (root.childs[3].childs).Add(newNode(8));
    (root.childs[3].childs).Add(newNode(9));
   
    Console.Write(kthSmallestElement(root, 3));
  }
}
 
// This code is contributed by divyeshrabadiya07.

Javascript

<script>
    // Javascript program for the above approach
     
    // Structure of a node
    class Node
    {
        constructor(data) {
           this.childs = [];
           this.data = data;
        }
    }
     
    // Global variable set to Maximum
    let MinimumElement = Number.MAX_VALUE;
 
    // Function that gives the smallest
    // element under the range of key
    function smallestEleUnderRange(root, data)
    {
        if (root.data > data) {
            MinimumElement = Math.min(root.data, MinimumElement);
        }
        for(let child = 0; child < (root.childs).length; child++) {
            smallestEleUnderRange(root.childs[child], data);
        }
    }
 
    // Function to find the Kth smallest element
    function kthSmallestElement(root, k)
    {
        let ans = Number.MIN_VALUE;
        for (let i = 0; i < k; i++) {
            smallestEleUnderRange(root, ans);
            ans = MinimumElement;
            MinimumElement = Number.MAX_VALUE;
        }
        return ans;
    }
 
    // Function to create a new node
    function newNode(data)
    {
        let temp = new Node(data);
        return temp;
    }
     
    /*   Let us create below tree
     *              10
     *        /   /    \   \
     *        2  34    56   100
     *       / \         |   /  | \
     *      77  88       1   7  8  9
     */
  
    let root = newNode(10);
    (root.childs).push(newNode(2));
    (root.childs).push(newNode(34));
    (root.childs).push(newNode(56));
    (root.childs).push(newNode(100));
    (root.childs[0].childs).push(newNode(77));
    (root.childs[0].childs).push(newNode(88));
    (root.childs[2].childs).push(newNode(1));
    (root.childs[3].childs).push(newNode(7));
    (root.childs[3].childs).push(newNode(8));
    (root.childs[3].childs).push(newNode(9));
  
    document.write(kthSmallestElement(root, 3));
     
    // This code is contributed by rameshtravel07.
</script>
Producción: 

7

 

Complejidad de tiempo: O(N * K) donde N es el número de Nodes en el árbol dado.
Espacio auxiliar: O(1), pero la pila recursiva usa un máximo de espacio O(N).

Publicación traducida automáticamente

Artículo escrito por shrayansh95 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *