Удаление дубликатов в массиве с помощью BST

Опубликовано: 1 Декабря, 2021

Учитывая массив целых чисел arr [], задача состоит в том, чтобы удалить дубликаты из данного массива.

Примеры :

 Ввод: arr [] = {1, 2, 3, 2, 5, 4, 4}
Вывод: arr [] = {1, 2, 3, 4, 5} 

Ввод: arr [] = {127, 234, 127, 654, 355, 789, 355, 355, 999, 654}
Вывод: arr [] = {127, 234, 355, 654, 789, 999}
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Дубликаты в массиве можно удалить с помощью дерева двоичного поиска. Идея состоит в том, чтобы создать дерево двоичного поиска с использованием элементов массива с условием, что первый элемент считается корневым (родительским) элементом, и когда появляется элемент «меньше», чем корневой, он становится левым дочерним, а элемент « больше », чем корень, становится правым потомком корня. Поскольку условия «равно» не существует, дубликаты автоматически удаляются, когда мы формируем двоичное дерево поиска из элементов массива.

For the array, arr[] = {1, 2, 3, 2, 5, 4, 4}
BST will be: 
 

 

Подход:

  • Сформируйте BST, используя элементы массива
  • Отобразите элементы, используя любой метод обхода дерева.

Ниже представлена реализация описанного выше подхода.

C ++

// C++ Program of above implementation
#include <iostream>
using namespace std;
// Struct declaration
struct Node {
data; int
struct Node* left;
struct Node* right;
};
// Node creation
struct Node* newNode( data) int
{
struct Node* nn
= new Node;
nn->data = data;
nn->left = NULL;
nn->right = NULL;
return nn;
}
// Function to insert data in BST
struct Node* insert( struct Node* root, data) int
{
if (root == NULL)
return newNode(data);
else {
if (data < root->data)
root->left = insert(root->left, data);
if (data > root->data)
root->right = insert(root->right, data);
return root;
}
}
// InOrder function to display value of array
// in sorted order
void inOrder( struct Node* root)
{
if (root == NULL)
return ;
else {
inOrder(root->left);
cout << root->data << " " ;
inOrder(root->right);
}
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 2, 5, 4, 4 };
// Finding size of array arr[]
int n = sizeof (arr) / sizeof (arr[0]);
struct Node* root = NULL;
for ( int i = 0; i < n; i++) {
// Insert element of arr[] in BST
root = insert(root, arr[i]);
}
// Inorder Traversal to print nodes of Tree
inOrder(root);
return 0;
}
// This code is contributed by shivanisingh

C

// C Program of above implementation
#include <stdio.h>
#include <stdlib.h>
// Struct declaration
struct Node {
data; int
struct Node* left;
struct Node* right;
};
// Node creation
struct Node* newNode( data) int
{
struct Node* nn
= ( struct Node*)( malloc ( sizeof ( struct Node)));
nn->data = data;
nn->left = NULL;
nn->right = NULL;
return nn;
}
// Function to insert data in BST
struct Node* insert( struct Node* root, data) int
{
if (root == NULL)
return newNode(data);
else {
if (data < root->data)
root->left = insert(root->left, data);
if (data > root->data)
root->right = insert(root->right, data);
return root;
}
}
// InOrder function to display value of array
// in sorted order
void inOrder( struct Node* root)
{
if (root == NULL)
return ;
else {
inOrder(root->left);
printf ( "%d " , root->data);
inOrder(root->right);
}
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 2, 5, 4, 4 };
// Finding size of array arr[]
int n = sizeof (arr) / sizeof (arr[0]);
struct Node* root = NULL;
for ( int i = 0; i < n; i++) {
// Insert element of arr[] in BST
root = insert(root, arr[i]);
}
// Inorder Traversal to print nodes of Tree
inOrder(root);
return 0;
}

Ява

// Java implementation of the approach
import java.util.Scanner;
// Node declaration
class Node
{
data; int
public Node left;
public Node right;
Node( data) int
{
this .data = data;
left = right = null ;
}
}
class GFG
{
// Function to insert data in BST
public static Node insert(Node root, data) int
{
if (root == null )
return new Node(data);
if (data < root.data)
root.left = insert(root.left, data);
if (data > root.data)
root.right = insert(root.right, data);
return root;
}
// InOrder function to display value of array
// in sorted order
public static void inOrder(Node root)
{
if (root == null )
return ;
inOrder(root.left);
System.out.print(root.data+ " " );
inOrder(root.right);
}
// Driver Code
public static void main(String []args){
int arr[] = { 1 , 2 , 3 , 2 , 5 , 4 , 4 };
// Finding size of array arr[]
int n = arr.length;
Node root = null ;
for ( int i = 0 ; i < n; i++)
{
// Insert element of arr[] in BST
root = insert(root,arr[i]);
}
// Inorder Traversal to print nodes of Tree
inOrder(root);
}
}
// This code is contributed by anishma

Python3

# Python3 implementation of the approach
# Binary tree node consists of data, a
# pointer to the left child and a
# pointer to the right child
class newNode :
def __init__( self ,data) :
self .data = data;
self .left = None ;
self .right = None ;
# Function to insert data in BST
def insert(root, data) :
if (root = = None ) :
return newNode(data);
else :
if (data < root.data) :
root.left = insert(root.left, data);
if (data > root.data) :
root.right = insert(root.right, data);
return root;
# InOrder function to display value of array
# in sorted order
def inOrder(root) :
if (root = = None ) :
return ;
else :
inOrder(root.left);
print (root.data, end = " " );
inOrder(root.right);
# Driver code
if __name__ = = "__main__" :
arr = [ 1 , 2 , 3 , 2 , 5 , 4 , 4 ];
# Finding size of array arr[]
n = len (arr);
root = None ;
for i in range (n) :
# Insert element of arr[] in BST
root = insert(root, arr[i]);
# Inorder Traversal to print nodes of Tree
inOrder(root);
# This code is contributed by AnkitRai01

C #

// C# program of above implementation
using System;
// Node declaration
public class Node
{
public data; int
public Node left;
public Node right;
public Node( data) int
{
this .data = data;
left = right = null ;
}
}
class GFG{
// Function to insert data in BST
public static Node insert(Node root, data) int
{
if (root == null )
return new Node(data);
if (data < root.data)
root.left = insert(root.left, data);
if (data > root.data)
root.right = insert(root.right, data);
return root;
}
// InOrder function to display value of array
// in sorted order
public static void inOrder(Node root)
{
if (root == null )
return ;
inOrder(root.left);
Console.Write(root.data + " " );
inOrder(root.right);
}
// Driver Code
static void Main()
{
int [] arr = { 1, 2, 3, 2, 5, 4, 4 };
// Finding size of array arr[]
int n = arr.Length;
Node root = null ;
for ( int i = 0; i < n; i++)
{
// Insert element of arr[] in BST
root = insert(root, arr[i]);
}
// Inorder Traversal to print nodes of Tree
inOrder(root);
}
}
// This code is contributed by divyeshrabadiya07
Выход:
 1 2 3 4 5

Сложность времени: O (N), где N - размер данного массива.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Язык программирования Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023