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>
Producción:
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