Dada una array arr[] de N enteros. la tarea es encontrar el número mínimo de operaciones requeridas para hacer que todos los elementos de la array sean distintos usando las siguientes operaciones.
- Elimine un elemento del inicio de la array arr[] y agregue cualquier número entero al final.
- Elimine un elemento del final de la array arr[] y anteponga cualquier número entero al principio.
Ejemplos :
Entrada : arr[] = {1, 3, 3, 5, 1, 9, 4, 1}
Salida : 4
Explicación : elimine 1 del final y agregue 5 al inicio [5, 1, 3, 3, 5, 1, 9, 4]
Retire 5 del inicio y agregue 7 al final [1, 3, 3, 5, 1, 9, 4, 7]
Retire 1 del inicio y agregue 8 al final [3, 3, 5, 1, 9, 4, 7, 8]
Retire 3 del principio y agregue 2 al final [3, 5, 1, 9, 4, 7, 8, 2]Entrada : arr[] = {1, 2, 3, 5, 4}
Salida : 0
Enfoque : para resolver el problema, siga la idea y los pasos a continuación:
- Al principio, encuentre el subarreglo que contiene todos los caracteres únicos y almacene su índice inicial en i y el índice final en j ,
- Ahora, aplique la fórmula 2*min(i, N – j – 1) + max(i, N – j – 1) y devuelva la respuesta,
- ¿Por qué funciona la fórmula?
- Como tenemos que eliminar los elementos desde el inicio hasta la i y desde la j hasta el final, elija cuál es el mínimo y luego agregue el doble de eso con el máximo.
- Hay un caso extremo, donde el subarreglo de tamaño máximo múltiple viene y luego da preferencia a ese subarreglo cuyo índice inicial es 0 o cuyo índice final es
N-1.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Primero, busque el subarreglo de tamaño máximo de todos los caracteres únicos .
- Encuentre el par {i, j} , es decir, el índice del primer y último elemento del subarreglo deseado, respectivamente.
- Aplica la fórmula, 2*min(i, N – j – 1) + max(i, N – j – 1) y devuélvelo como la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find max subarray
// with all unique characters
pair<int, int> findMax(int a[], int n)
{
unordered_map<int, int> index;
int ans = 0, x = -1, y = -1;
for (int i = 0, j = 0; i < n; i++) {
j = max(index[a[i]], j);
if ((i - j + 1) >= ans) {
// If there are multiple
// max subarray
if ((i - j + 1) == ans) {
// If the subarray is touching
// the edge of the array
if (i == (n - 1) || j == 0) {
ans = i - j + 1;
x = i;
y = j;
}
}
// If there is new max subarray
else {
ans = i - j + 1;
x = i;
y = j;
}
}
index[a[i]] = i + 1;
}
// Return the starting and ending indices
// of max size subarray
return { x, y };
}
// Function to find minimum operations
// to make all the characters of arr unique
int findMinOperations(int* arr, int n)
{
pair<int, int> p = findMax(arr, n);
int i = p.second;
int j = p.first;
return 2 * min(i, n - j - 1)
+ max(i, n - j - 1);
}
// Drivers code
int main()
{
int arr[] = { 1, 3, 3, 5, 1, 9, 4, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << findMinOperations(arr, N);
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class pair {
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
class GFG {
// Function to find max subarray with all unique
// characters.
public static pair findMax(int[] a, int n)
{
HashMap<Integer, Integer> index
= new HashMap<Integer, Integer>();
int ans = 0, x = -1, y = -1;
for (int i = 0, j = 0; i < n; i++) {
if (index.get(a[i]) != null) {
j = Math.max(index.get(a[i]), j);
}
if ((i - j + 1) >= ans) {
// If there are multiple max subarray
if ((i - j + 1) == ans) {
// If the subarray is touching the edge
// of the array
if (i == (n - 1) || j == 0) {
ans = i - j + 1;
x = i;
y = j;
}
}
// If there is new max subarray
else {
ans = i - j + 1;
x = i;
y = j;
}
}
index.put(a[i], i + 1);
}
// Return the starting and ending indices of max
// size subarray
return new pair(x, y);
}
// Function to find minimum operations to make all the
// characters of arr unique
public static int findMinOperations(int[] arr, int n)
{
pair p = findMax(arr, n);
int i = p.second;
int j = p.first;
return 2 * Math.min(i, n - j - 1)
+ Math.max(i, n - j - 1);
}
public static void main(String[] args)
{
int[] arr = { 1, 3, 3, 5, 1, 9, 4, 1 };
int N = arr.length;
// Function call
System.out.print(findMinOperations(arr, N));
}
}
// This code is contributed by lokesh (lokeshmvs21).
C#
// C# code to implement the above approach
using System;
using System.Collections.Generic;
class pair {
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
public class GFG {
// Function to find max subarray with all unique
// characters.
static pair findMax(int[] a, int n)
{
Dictionary<int, int> index
= new Dictionary<int, int>();
int ans = 0, x = -1, y = -1;
for (int i = 0, j = 0; i < n; i++) {
if (index.ContainsKey(a[i])) {
j = Math.Max(index[a[i]], j);
}
if ((i - j + 1) >= ans) {
// If there are multiple max subarray
if ((i - j + 1) == ans) {
// If the subarray is touching the edge
// of the array
if (i == (n - 1) || j == 0) {
ans = i - j + 1;
x = i;
y = j;
}
}
// If there is new max subarray
else {
ans = i - j + 1;
x = i;
y = j;
}
}
if(index.ContainsKey(a[i]))
index[a[i]] = i+1;
else
index.Add(a[i], i + 1);
}
// Return the starting and ending indices of max
// size subarray
return new pair(x, y);
}
// Function to find minimum operations to make all the
// characters of arr unique
public static int findMinOperations(int[] arr, int n)
{
pair p = findMax(arr, n);
int i = p.second;
int j = p.first;
return 2 * Math.Min(i, n - j - 1)
+ Math.Max(i, n - j - 1);
}
public static void Main(String[] args)
{
int[] arr = { 1, 3, 3, 5, 1, 9, 4, 1 };
int N = arr.Length;
// Function call
Console.Write(findMinOperations(arr, N));
}
}
// This code contributed by shikhasingrajput
Producción
4
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA