Dada una array arr[] de N enteros distintos, la tarea es reemplazar cada elemento por el más pequeño entre todos los demás elementos restantes de la array.
Ejemplos:
Entrada: arr[] = { 4, 2, 1, 3 }
Salida: arr[]= { 1, 1, 2, 1 }
Explicación:
Para arr[0], el menor de los elementos restantes es 1. Entonces arr [0] se reemplaza por 1.
Para arr[1], el más pequeño de los elementos restantes es 1. Entonces arr[1] se reemplaza por 1.
Para arr[2], el más pequeño de los elementos restantes es 2. Entonces arr[2] se reemplaza por 2.
Para arr[3], el elemento más pequeño de los restantes es 1. Entonces arr[3] se reemplaza por 1.
Entrada: arr[] = { 1, 5, 2, 4 }
Salida: arr[] = { 2, 1, 1, 1 }
Enfoque ingenuo:
Ejecute un bucle anidado y encuentre el más pequeño de todos los demás elementos para cada elemento y almacénelo.
Complejidad de tiempo: O(N 2 )
Enfoque eficiente:
- Recorre la array y encuentra los dos elementos más pequeños de la array.
- Atraviese la array nuevamente, ahora reemplace el elemento más pequeño con el segundo elemento más pequeño y reemplace todos los demás elementos en la array con el elemento más pequeño.
- Imprime la array modificada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C# implementation to find the
// maximum array sum by concatenating
// corresponding elements of given two arrays
using System;
class GFG{
// Function to join the two numbers
static int joinNumbers(int numA, int numB)
{
int revB = 0;
// Loop to reverse the digits
// of the one number
while (numB > 0)
{
revB = revB * 10 + (numB % 10);
numB = numB / 10;
}
// Loop to join two numbers
while (revB > 0)
{
numA = numA * 10 + (revB % 10);
revB = revB / 10;
}
return numA;
}
// Function to find the maximum array sum
static int findMaxSum(int []A, int []B, int n)
{
int []maxArr = new int[n];
// Loop to iterate over the two
// elements of the array
for(int i = 0; i < n; ++i)
{
int X = joinNumbers(A[i], B[i]);
int Y = joinNumbers(B[i], A[i]);
int mx = Math.Max(X, Y);
maxArr[i] = mx;
}
// Find the array sum
int maxAns = 0;
for(int i = 0; i < n; i++)
{
maxAns += maxArr[i];
}
// Return the array sum
return maxAns;
}
// Driver Code
public static void Main(String []args)
{
int N = 5;
int []A = { 11, 23, 38, 43, 59 };
int []B = { 36, 24, 17, 40, 56 };
Console.WriteLine(findMaxSum(A, B, N));
}
}
// This code is contributed by Rajput-Ji
Java
// Java code for the above approach.
import java.util.*;
class GFG {
static void ReplaceElements(
int[] arr, int n)
{
// There should be atleast
// two elements
if (n < 2) {
System.out.println(
"Invalid Input");
return;
}
int firstSmallest
= Integer.MAX_VALUE;
int secondSmallest
= Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
// If current element is smaller
// than firstSmallest then update
// both firstSmallest
// and secondSmallest
if (arr[i] < firstSmallest) {
secondSmallest = firstSmallest;
firstSmallest = arr[i];
}
// If arr[i] is in between
// firstSmallest and secondSmallest
// then update secondSmallest
else if (arr[i] < secondSmallest
&& arr[i] != firstSmallest)
secondSmallest = arr[i];
}
// Replace every element by
// smallest of all other elements
for (int i = 0; i < n; i++) {
if (arr[i] != firstSmallest)
arr[i] = firstSmallest;
else
arr[i] = secondSmallest;
}
// Print the modified array.
for (int i = 0; i < n; ++i) {
System.out.print(arr[i]
+ ", ");
}
}
// Driver code
public static void main(
String[] args)
{
int arr[] = { 4, 2, 1, 3 };
int n = arr.length;
ReplaceElements(arr, n);
}
}
Python3
# Python3 code for the above approach.
def ReplaceElements(arr, n):
# There should be atleast
# two elements
if (n < 2):
print("Invalid Input")
return
firstSmallest = 10 ** 18
secondSmallest = 10 ** 18
for i in range(n):
# If current element is smaller
# than firstSmallest then update
# both firstSmallest
# and secondSmallest
if (arr[i] < firstSmallest):
secondSmallest = firstSmallest
firstSmallest = arr[i]
# If arr[i] is in between
# firstSmallest and secondSmallest
# then update secondSmallest
elif (arr[i] < secondSmallest and
arr[i] != firstSmallest):
secondSmallest = arr[i]
# Replace every element by
# smallest of all other elements
for i in range(n):
if (arr[i] != firstSmallest):
arr[i] = firstSmallest
else:
arr[i] = secondSmallest
# Print the modified array.
for i in arr:
print(i, end = ", ")
# Driver code
if __name__ == '__main__':
arr= [ 4, 2, 1, 3 ]
n = len(arr)
ReplaceElements(arr, n)
# This code is contributed by mohit kumar 29
C#
// C# code for the above approach.
using System;
class GFG{
static void ReplaceElements(int[] arr, int n)
{
// There should be atleast
// two elements
if (n < 2)
{
Console.Write("Invalid Input");
return;
}
int firstSmallest = Int32.MaxValue;
int secondSmallest = Int32.MaxValue;
for(int i = 0; i < n; i++)
{
// If current element is smaller
// than firstSmallest then update
// both firstSmallest
// and secondSmallest
if (arr[i] < firstSmallest)
{
secondSmallest = firstSmallest;
firstSmallest = arr[i];
}
// If arr[i] is in between
// firstSmallest and secondSmallest
// then update secondSmallest
else if (arr[i] < secondSmallest &&
arr[i] != firstSmallest)
secondSmallest = arr[i];
}
// Replace every element by
// smallest of all other elements
for(int i = 0; i < n; i++)
{
if (arr[i] != firstSmallest)
arr[i] = firstSmallest;
else
arr[i] = secondSmallest;
}
// Print the modified array.
for(int i = 0; i < n; ++i)
{
Console.Write(arr[i] + ", ");
}
}
// Driver code
public static void Main()
{
int []arr = { 4, 2, 1, 3 };
int n = arr.Length;
ReplaceElements(arr, n);
}
}
// This code is contributed by Nidhi_Biet
Javascript
<script>
// Javascript code for the above approach.
function ReplaceElements(arr, n)
{
// There should be atleast
// two elements
if (n < 2)
{
document.write(
"Invalid Input<br>");
return;
}
let firstSmallest
= Number.MAX_VALUE;
let secondSmallest
= Number.MAX_VALUE;
for (let i = 0; i < n; i++)
{
// If current element is smaller
// than firstSmallest then update
// both firstSmallest
// and secondSmallest
if (arr[i] < firstSmallest)
{
secondSmallest = firstSmallest;
firstSmallest = arr[i];
}
// If arr[i] is in between
// firstSmallest and secondSmallest
// then update secondSmallest
else if (arr[i] < secondSmallest
&& arr[i] != firstSmallest)
secondSmallest = arr[i];
}
// Replace every element by
// smallest of all other elements
for (let i = 0; i < n; i++) {
if (arr[i] != firstSmallest)
arr[i] = firstSmallest;
else
arr[i] = secondSmallest;
}
// Print the modified array.
for (let i = 0; i < n; ++i) {
document.write(arr[i]
+ ", ");
}
}
// Driver code
let arr=[ 4, 2, 1, 3 ];
let n = arr.length;
ReplaceElements(arr, n);
// This code is contributed by unknown2108.
</script>
Producción:
1, 1, 2, 1,
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)