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: 7
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