Dado un árbol de array N que consta de N Nodes y un número entero K , la tarea es encontrar el elemento más grande K en el árbol N-ario dado .
Ejemplos:
Entrada: K = 3
Salida: 77
Explicación:
El tercer elemento más grande en el árbol de array N dado es 77.Entrada: K = 4
Salida: 3
Enfoque: El problema dado se puede resolver encontrando el elemento más grande en el rango dado por K veces y continuando actualizando el final del rango al elemento más grande encontrado hasta el momento. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos, largeELE como INT_MIN .
- Defina una función , diga más grande EleUnderRange (raíz, datos) y realice los siguientes pasos:
- Si el valor de la raíz actual es menor que los datos, actualice el valor de la mayor ELe como el máximo de la mayor ELe y el valor de la raíz actual.
- Iterar sobre todos los elementos secundarios de la raíz actual y llamar recursivamente a la función más grandeEleUnderRange(child, data) .
- Inicialice una variable, digamos, ans como INT_MAX para almacenar el elemento K -ésimo más grande.
- Iterar sobre el rango [0, K – 1] llamar recursivamente a la función largeEleUnderRange(root, ans) y actualizar el valor de ans como largeELe y largeELe como INT_MIN .
- Después de completar los pasos anteriores, imprima el valor de ans como el valor máximo resultante de K.
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 N-array Tree class Node { public: int data; vector<Node*> childs; }; // Stores the minimum element // in the recursive call int largestELe = INT_MIN; // Function to find the largest // element under the range of key void largestEleUnderRange( Node* root, int data) { // If the current root's value // is less than data if (root->data < data) { largestELe = max(root->data, largestELe); } // Iterate over all the childrens for (Node* child : root->childs) { // Update under current range largestEleUnderRange(child, data); } } // Function to find the Kth Largest // element in the given N-ary Tree void KthLargestElement(Node* root, int K) { // Stores the resultant // Kth maximum element int ans = INT_MAX; // Iterate over the range [0, K] for (int i = 0; i < K; i++) { // Recursively call for // finding the maximum element // from the given range largestEleUnderRange(root, ans); // Update the value of // ans and largestEle ans = largestELe; largestELe = INT_MIN; } // Print the result cout << ans; } // Function to create a new node Node* newNode(int data) { Node* temp = new Node(); temp->data = data; // Return the created node return temp; } // Driver Code int main() { /* Create below the 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)); int K = 3; KthLargestElement(root, K); return 0; }
Java
// Java program for the above approach import java.util.*; public class Main { // Structure of N-array Tree static class Node { public int data; public Vector<Node> childs = new Vector<Node>(); } // Function to create a new node static Node newNode(int data) { Node temp = new Node(); temp.data = data; return temp; } // Stores the minimum element // in the recursive call static int largestELe = Integer.MIN_VALUE; // Function to find the largest // element under the range of key static void largestEleUnderRange(Node root, int data) { // If the current root's value // is less than data if (root.data < data) { largestELe = Math.max(root.data, largestELe); } // Iterate over all the childrens for (int child = 0; child < root.childs.size(); child++) { // Update under current range largestEleUnderRange(root.childs.get(child), data); } } // Function to find the Kth Largest // element in the given N-ary Tree static void KthLargestElement(Node root, int K) { // Stores the resultant // Kth maximum element int ans = Integer.MAX_VALUE; // Iterate over the range [0, K] for (int i = 0; i < K; i++) { // Recursively call for // finding the maximum element // from the given range largestEleUnderRange(root, ans); // Update the value of // ans and largestEle ans = largestELe; largestELe = Integer.MIN_VALUE; } // Print the result System.out.print(ans); } public static void main(String[] args) { /* Create below the 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)); int K = 3; KthLargestElement(root, K); } } // This code is contributed by suresh07.
Python3
# Python3 program for the above approach import sys # Structure of N-array Tree class Node: # Constructor to set the data of # the newly created tree node def __init__(self, data): self.data = data self.childs = [] # Stores the minimum element # in the recursive call largestELe = -sys.maxsize # Function to find the largest # element under the range of key def largestEleUnderRange(root, data): global largestELe # If the current root's value # is less than data if (root.data < data) : largestELe = max(root.data, largestELe) # Iterate over all the childrens for child in range(len(root.childs)): # Update under current range largestEleUnderRange(root.childs[child], data) # Function to find the Kth Largest # element in the given N-ary Tree def KthLargestElement(root, K): global largestELe # Stores the resultant # Kth maximum element ans = sys.maxsize # Iterate over the range [0, K] for i in range(K): # Recursively call for # finding the maximum element # from the given range largestEleUnderRange(root, ans) # Update the value of # ans and largestEle ans = largestELe largestELe = -sys.maxsize # Print the result print(ans) """ Create below the tree * 10 * / / \ \ * 2 34 56 100 * / \ | / | \ * 77 88 1 7 8 9 """ root = Node(10) (root.childs).append(Node(2)); (root.childs).append(Node(34)); (root.childs).append(Node(56)); (root.childs).append(Node(100)); (root.childs[0].childs).append(Node(77)) (root.childs[0].childs).append(Node(88)) (root.childs[2].childs).append(Node(1)) (root.childs[3].childs).append(Node(7)) (root.childs[3].childs).append(Node(8)) (root.childs[3].childs).append(Node(9)) K = 3 KthLargestElement(root, K) # This code is contributed by rameshtravel07.
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Structure of N-array Tree class Node { public int data; public List<Node> childs = new List<Node>(); }; // Function to create a new node static Node newNode(int data) { Node temp = new Node(); temp.data = data; return temp; } // Stores the minimum element // in the recursive call static int largestELe = Int32.MinValue; // Function to find the largest // element under the range of key static void largestEleUnderRange(Node root, int data) { // If the current root's value // is less than data if (root.data < data) { largestELe = Math.Max(root.data, largestELe); } // Iterate over all the childrens for (int child = 0; child < root.childs.Count; child++) { // Update under current range largestEleUnderRange(root.childs[child], data); } } // Function to find the Kth Largest // element in the given N-ary Tree static void KthLargestElement(Node root, int K) { // Stores the resultant // Kth maximum element int ans = Int32.MaxValue; // Iterate over the range [0, K] for (int i = 0; i < K; i++) { // Recursively call for // finding the maximum element // from the given range largestEleUnderRange(root, ans); // Update the value of // ans and largestEle ans = largestELe; largestELe = Int32.MinValue; } // Print the result Console.Write(ans); } static void Main() { /* Create below the 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)); int K = 3; KthLargestElement(root, K); } } // This code is contributed by decode2207.
Javascript
<script> // JavaScript program for the above approach // Structure of N-array Tree class Node { constructor(data) { this.childs = []; this.data = data; } } // Stores the minimum element // in the recursive call let largestELe = Number.MIN_VALUE; // Function to find the largest // element under the range of key function largestEleUnderRange(root, data) { // If the current root's value // is less than data if (root.data < data) { largestELe = Math.max(root.data, largestELe); } // Iterate over all the childrens for (let child = 0; child < root.childs.length; child++) { // Update under current range largestEleUnderRange(root.childs[child], data); } } // Function to find the Kth Largest // element in the given N-ary Tree function KthLargestElement(root, K) { // Stores the resultant // Kth maximum element let ans = Number.MAX_VALUE; // Iterate over the range [0, K] for (let i = 0; i < K; i++) { // Recursively call for // finding the maximum element // from the given range largestEleUnderRange(root, ans); // Update the value of // ans and largestEle ans = largestELe; largestELe = Number.MIN_VALUE; } // Print the result document.write(ans); } // Function to create a new node function newNode(data) { let temp = new Node(data); // Return the created node return temp; } /* Create below the 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)); let K = 3; KthLargestElement(root, K); </script>
77
Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shrayansh95 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA