- Dada una array arr[] de 2*N enteros tal que consta de todos los elementos junto con los valores dobles de otra array, digamos A[] , la tarea es encontrar la array A[] .
Ejemplos:
Entrada: arr[] = {4, 1, 18, 2, 9, 8}
Salida: 1 4 9
Explicación:
después de tomar los valores dobles de 1, 4 y 9 y luego agregarlos a la array original, todos los elementos de la array dada se obtienen array arr[]Entrada: arr[] = {4, 1, 2, 2, 8, 2, 4, 4}
Salida: 1 2 2 4
Enfoque: el problema dado se puede resolver contando la frecuencia de los elementos de la array en los elementos de la array HashMap y se puede observar que el elemento más pequeño de la array siempre será parte de la array original, por lo tanto, se puede incluir en la array. lista de resultados res[] . El elemento con un valor doble del elemento más pequeño será el elemento duplicado que no forma parte de la array original, por lo que su frecuencia se puede reducir del mapa. Se pueden seguir los siguientes pasos para resolver el problema:
- Ordenar la array dada arr[] en orden ascendente
- Iterar a través de los elementos de la array y almacenar los números y sus frecuencias en un hashmap
- Crear una lista de resultados res[] para almacenar los elementos presentes en la lista original
- Agregue el primer elemento en la lista de resultados y reduzca la frecuencia del elemento que tiene un valor doble del primer elemento.
- Recorra la array y verifique la frecuencia de cada elemento en el mapa:
- Si la frecuencia es mayor que 0, agregue el elemento en la lista de resultados y disminuya la frecuencia.
- De lo contrario, omita el elemento y siga adelante porque es un valor doble y no forma parte de la array original.
- Después de completar los pasos anteriores, imprima los elementos en la lista res[] .
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;
// Function to find the original array
// from the doubled array
vector<int> findOriginal(vector<int>& arr)
{
// Stores the numbers and
// their frequency
map<int, int> numFreq;
// Add number with their frequencies
// in the hashmap
for (int i = 0; i < arr.size(); i++) {
numFreq[arr[i]]++;
}
// Sort the array
sort(arr.begin(), arr.end());
// Initialize an arraylist
vector<int> res;
for (int i = 0; i < arr.size(); i++) {
// Get the frequency of the number
int freq = numFreq[arr[i]];
if (freq > 0) {
// Element is of original array
res.push_back(arr[i]);
// Decrement the frequency of
// the number
numFreq[arr[i]]--;
int twice = 2 * arr[i];
// Decrement the frequency of
// the number having double value
numFreq[twice]--;
}
}
// Return the resultant string
return res;
}
// Driver Code
int main()
{
vector<int> arr = { 4, 1, 2, 2, 2, 4, 8, 4 };
vector<int> res = findOriginal(arr);
// Print the result list
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the original array
// from the doubled array
public static List<Integer>
findOriginal(int[] arr)
{
// Stores the numbers and
// their frequency
Map<Integer, Integer> numFreq
= new HashMap<>();
// Add number with their frequencies
// in the hashmap
for (int i = 0; i < arr.length; i++) {
numFreq.put(
arr[i],
numFreq.getOrDefault(arr[i], 0)
+ 1);
}
// Sort the array
Arrays.sort(arr);
// Initialize an arraylist
List<Integer> res = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
// Get the frequency of the number
int freq = numFreq.get(arr[i]);
if (freq > 0) {
// Element is of original array
res.add(arr[i]);
// Decrement the frequency of
// the number
numFreq.put(arr[i], freq - 1);
int twice = 2 * arr[i];
// Decrement the frequency of
// the number having double value
numFreq.put(
twice,
numFreq.get(twice) - 1);
}
}
// Return the resultant string
return res;
}
// Driver Code
public static void main(String[] args)
{
List<Integer> res = findOriginal(
new int[] { 4, 1, 2, 2, 2, 4, 8, 4 });
// Print the result list
for (int i = 0; i < res.size(); i++) {
System.out.print(
res.get(i) + " ");
}
}
}
Python3
# Python program for the above approach
# Function to find the original array
# from the doubled array
def findOriginal(arr):
# Stores the numbers and
# their frequency
numFreq = {}
# Add number with their frequencies
# in the hashmap
for i in range(0, len(arr)):
if (arr[i] in numFreq):
numFreq[arr[i]] += 1
else:
numFreq[arr[i]] = 1
# Sort the array
arr.sort()
# Initialize an arraylist
res = []
for i in range(0, len(arr)):
# Get the frequency of the number
freq = numFreq[arr[i]]
if (freq > 0):
# Element is of original array
res.append(arr[i])
# Decrement the frequency of
# the number
numFreq[arr[i]] -= 1
twice = 2 * arr[i]
# Decrement the frequency of
# the number having double value
numFreq[twice] -= 1
# Return the resultant string
return res
# Driver Code
arr = [4, 1, 2, 2, 2, 4, 8, 4]
res = findOriginal(arr)
# Print the result list
for i in range(0, len(res)):
print(res[i], end=" ")
# This code is contributed by _Saurabh_Jaiswal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the original array
// from the doubled array
public static List<int> findOriginal(int[] arr)
{
// Stores the numbers and
// their frequency
Dictionary<int, int> numFreq = new Dictionary<int, int>();
// Add number with their frequencies
// in the hashmap
for (int i = 0; i < arr.Length; i++) {
if(numFreq.ContainsKey(arr[i])){
numFreq[arr[i]] = numFreq[arr[i]] + 1;
}else{
numFreq.Add(arr[i], 1);
}
}
// Sort the array
Array.Sort(arr);
// Initialize an arraylist
List<int> res = new List<int>();
for (int i = 0; i < arr.Length; i++) {
// Get the frequency of the number
int freq = numFreq[arr[i]];
if (freq > 0) {
// Element is of original array
res.Add(arr[i]);
// Decrement the frequency of
// the number
numFreq[arr[i]] = freq - 1;
int twice = 2 * arr[i];
// Decrement the frequency of
// the number having double value
numFreq[twice] = numFreq[twice] - 1;
}
}
// Return the resultant string
return res;
}
// Driver Code
public static void Main()
{
List<int> res = findOriginal(new int[] { 4, 1, 2, 2, 2, 4, 8, 4 });
// Print the result list
for (int i = 0; i < res.Count; i++) {
Console.Write(res[i] + " ");
}
}
}
// This code is contributed by gfgking.
Javascript
<script>
// Javascript program for the above approach
// Function to find the original array
// from the doubled array
function findOriginal(arr)
{
// Stores the numbers and
// their frequency
let numFreq = new Map();
// Add number with their frequencies
// in the hashmap
for (let i = 0; i < arr.length; i++) {
if (numFreq.has(arr[i])) {
numFreq.set(arr[i], numFreq.get(arr[i]) + 1);
} else {
numFreq.set(arr[i], 1);
}
}
// Sort the array
arr.sort((a, b) => a - b);
// Initialize an arraylist
let res = [];
for (let i = 0; i < arr.length; i++) {
// Get the frequency of the number
let freq = numFreq.get(arr[i]);
if (freq > 0) {
// Element is of original array
res.push(arr[i]);
// Decrement the frequency of
// the number
numFreq.set(arr[i], numFreq.get(arr[i]) - 1);
let twice = 2 * arr[i];
// Decrement the frequency of
// the number having double value
numFreq.set(twice, numFreq.get(twice) - 1);
}
}
// Return the resultant string
return res;
}
// Driver Code
let arr = [4, 1, 2, 2, 2, 4, 8, 4];
let res = findOriginal(arr);
// Print the result list
for (let i = 0; i < res.length; i++) {
document.write(res[i] + " ");
}
// This code is contributed by gfgking.
</script>
Producción:
1 2 2 4
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por darkphoenix349 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA