Dada una array no ordenada arr[] que consta de N números naturales y los números faltantes como 0 tal que arr[i] ≠ i , la tarea es encontrar y completar estos números faltantes sin cambiar el orden inicial. Tenga en cuenta que la array puede contener números del 1 al N solo una vez.
Ejemplos:
Entrada: arr[] = {7, 4, 0, 3, 0, 5, 1}
Salida: 7 4 6 3 2 5 1
Explicación:
En la array dada, los índices vacíos son 2 y 4. Entonces, los números faltantes que pueden llenar, para cumplir con los criterios arr[i] ≠ i, son 6 y 2 respectivamente.Entrada: arr[] = {2, 1, 0, 0, 0}
Salida: 2 1 4 5 3
Explicación:
En la array dada, los índices sin completar son 3, 4 y 5. Por lo tanto, los números faltantes que se pueden completar para cumplir los criterios arr[i] ≠ i, son 4, 5 y 3 respectivamente.
Acercarse:
- Almacene todos los índices sin llenar en una array unfilled_indices[] . es decir, para todo i tal que arr[i] = 0.
- También almacene todos los elementos que faltan en la array que falta [] . Esto se puede hacer insertando primero todos los elementos del 1 al N y luego eliminando todos los elementos que no sean 0
- Simplemente itere la array unfilled_indices[] y comience a asignar todos los elementos almacenados en la array faltante[] posiblemente tomando cada elemento desde atrás (para evitar que i obtenga arr[i] = i ).
- Ahora es posible que el máximo de un índice pueda obtener el mismo arr[i] = i . Simplemente intercambie con él cualquier otro elemento después de comprobar que el otro índice debería estar presente en unfilled_indices[] .
- Imprime la nueva array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print array
void printArray(int[], int);
// Function to fill the position
// with arr[i] = 0
void solve(int arr[], int n)
{
set<int> unfilled_indices;
set<int> missing;
// Inserting all elements in
// missing[] set from 1 to N
for (int i = 1; i < n; i++)
missing.insert(i);
for (int i = 1; i < n; i++) {
// Inserting unfilled positions
if (arr[i] == 0)
unfilled_indices.insert(i);
// Removing allocated_elements
else {
auto it = missing.find(arr[i]);
missing.erase(it);
}
}
auto it2 = missing.end();
it2--;
// Loop for filling the positions
// with arr[i] != i
for (auto it = unfilled_indices.begin();
it != unfilled_indices.end();
it++, it2--) {
arr[*it] = *it2;
}
int pos = 0;
// Checking for any arr[i] = i
for (int i = 1; i < n; i++) {
if (arr[i] == i) {
pos = i;
}
}
int x;
// Finding the suitable position
// in the array to swap with found i
// for which arr[i] = i
if (pos != 0) {
for (int i = 1; i < n; i++) {
if (pos != i) {
// Checking if the position
// is present in unfilled_position
if (unfilled_indices.find(i)
!= unfilled_indices.end()) {
// Swapping arr[i] & arr[pos]
// (arr[pos] = pos)
x = arr[i];
arr[i] = pos;
arr[pos] = x;
break;
}
}
}
}
printArray(arr, n);
}
// Function to Print the array
void printArray(int arr[], int n)
{
for (int i = 1; i < n; i++)
cout << arr[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 0, 7, 4, 0,
3, 0, 5, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
solve(arr, n);
return 0;
}
Java
// Java implementation of above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to fill the position
// with arr[i] = 0
static void solve(int arr[], int n)
{
Set<Integer> unfilled_indices = new HashSet<Integer>();
Set<Integer> missing = new HashSet<Integer>();
// Inserting all elements in
// missing[] set from 1 to N
for (int i = 1; i < n; i++)
{
missing.add(i);
}
for (int i = 1; i < n; i++)
{
// Inserting unfilled positions
if (arr[i] == 0)
{
unfilled_indices.add(i);
}
// Removing allocated_elements
else
{
missing.remove(arr[i]);
}
}
int[] mi = new int[missing.size()];
int l = 0;
for(int x:missing)
{
mi[l++] = x;
}
int m = missing.size();
// Loop for filling the positions
// with arr[i] != i
for(int it:unfilled_indices)
{
arr[it] = mi[m - 1];
m--;
}
int pos = 0;
// Checking for any arr[i] = i
for (int i = 1; i < n; i++)
{
if (arr[i] == i)
{
pos = i;
}
}
int x;
// Finding the suitable position
// in the array to swap with found i
// for which arr[i] = i
if (pos != 0)
{
for (int i = 1; i < n; i++)
{
if (pos != i)
{
// Checking if the position
// is present in unfilled_position
if(unfilled_indices.contains(i))
{
// Swapping arr[i] & arr[pos]
// (arr[pos] = pos)
x = arr[i];
arr[i] = pos;
arr[pos] = x;
break;
}
}
}
}
printArray(arr, n);
}
// Function to Print the array
static void printArray(int arr[], int n)
{
for (int i = 1; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}
// Driver Code
public static void main (String[] args)
{
int[] arr = { 0, 7, 4, 0,3, 0, 5, 1 };
int n = arr.length;
solve(arr, n);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation of above approach
# Function to fill the position
# with arr[i] = 0
def solve(arr, n):
unfilled_indices = {}
missing = {}
# Inserting all elements in
# missing[] set from 1 to N
for i in range(n):
missing[i] = 1
for i in range(1, n):
# Inserting unfilled positions
if (arr[i] == 0):
unfilled_indices[i] = 1
# Removing allocated_elements
else:
del missing[arr[i]]
it2 = list(missing.keys())
m = len(it2)
# Loop for filling the positions
# with arr[i] != i
for it in unfilled_indices:
arr[it] = it2[m - 1]
m -= 1
pos = 0
# Checking for any arr[i] = i
for i in range(1, n):
if (arr[i] == i):
pos = i
x = 0
# Finding the suitable position
# in the array to swap with found i
# for which arr[i] = i
if (pos != 0):
for i in range(1, n):
if (pos != i):
# Checking if the position
# is present in unfilled_position
if i in unfilled_indices:
# Swapping arr[i] & arr[pos]
# (arr[pos] = pos)
x = arr[i]
arr[i] = pos
arr[pos] = x
break
printArray(arr, n)
# Function to Print the array
def printArray(arr, n):
for i in range(1, n):
print(arr[i], end = " ")
# Driver Code
if __name__ == '__main__':
arr = [ 0, 7, 4, 0, 3, 0, 5, 1 ]
n = len(arr)
solve(arr, n)
# This code is contributed by mohit kumar 29
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to fill the position
// with arr[i] = 0
static void solve(int[] arr, int n)
{
HashSet<int> unfilled_indices = new HashSet<int>();
HashSet<int> missing = new HashSet<int>();
// Inserting all elements in
// missing[] set from 1 to N
for(int i = 1; i < n; i++)
{
missing.Add(i);
}
for(int i = 1; i < n; i++)
{
// Inserting unfilled positions
if (arr[i] == 0)
{
unfilled_indices.Add(i);
}
// Removing allocated_elements
else
{
missing.Remove(arr[i]);
}
}
int[] mi = new int[missing.Count];
int l = 0;
foreach(int x in missing)
{
mi[l++] = x;
}
int m = missing.Count;
// Loop for filling the positions
// with arr[i] != i
foreach(int it in unfilled_indices)
{
arr[it] = mi[m - 1];
m--;
}
int pos = 0;
// Checking for any arr[i] = i
for(int i = 1; i < n; i++)
{
if (arr[i] == i)
{
pos = i;
}
}
// Finding the suitable position
// in the array to swap with found i
// for which arr[i] = i
if (pos != 0)
{
for(int i = 1; i < n; i++)
{
if (pos != i)
{
// Checking if the position
// is present in unfilled_position
if (unfilled_indices.Contains(i))
{
// Swapping arr[i] & arr[pos]
// (arr[pos] = pos)
int x = arr[i];
arr[i] = pos;
arr[pos] = x;
break;
}
}
}
}
printArray(arr, n);
}
// Function to Print the array
static void printArray(int[] arr, int n)
{
for(int i = 1; i < n; i++)
{
Console.Write(arr[i] + " ");
}
}
// Driver Code
static public void Main()
{
int[] arr = { 0, 7, 4, 0, 3, 0, 5, 1 };
int n = arr.Length;
solve(arr, n);
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript implementation of above approach
// Function to fill the position
// with arr[i] = 0
function solve(arr,n)
{
let unfilled_indices = new Set();
let missing = new Set();
// Inserting all elements in
// missing[] set from 1 to N
for (let i = 1; i < n; i++)
{
missing.add(i);
}
for (let i = 1; i < n; i++)
{
// Inserting unfilled positions
if (arr[i] == 0)
{
unfilled_indices.add(i);
}
// Removing allocated_elements
else
{
missing.delete(arr[i]);
}
}
let mi = new Array(missing.size);
let l = 0;
for(let x of missing.values())
{
mi[l++] = x;
}
let m = missing.size;
// Loop for filling the positions
// with arr[i] != i
for(let it of unfilled_indices.values())
{
arr[it] = mi[m - 1];
m--;
}
let pos = 0;
// Checking for any arr[i] = i
for (let i = 1; i < n; i++)
{
if (arr[i] == i)
{
pos = i;
}
}
let x;
// Finding the suitable position
// in the array to swap with found i
// for which arr[i] = i
if (pos != 0)
{
for (let i = 1; i < n; i++)
{
if (pos != i)
{
// Checking if the position
// is present in unfilled_position
if(unfilled_indices.has(i))
{
// Swapping arr[i] & arr[pos]
// (arr[pos] = pos)
x = arr[i];
arr[i] = pos;
arr[pos] = x;
break;
}
}
}
}
printArray(arr, n);
}
// Function to Print the array
function printArray(arr,n)
{
for (let i = 1; i < n; i++)
{
document.write(arr[i] + " ");
}
}
// Driver Code
let arr=[0, 7, 4, 0,3, 0, 5, 1 ];
let n = arr.length;
solve(arr, n);
// This code is contributed by unknown2108
</script>
Producción:
7 4 6 3 2 5 1
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)