Dada una array arr[] de tamaño N donde arr[i] ≤ N, la tarea es encontrar el número mínimo de operaciones para ordenar la array en orden creciente donde En una operación puede seleccionar un entero X y:
- Mover todas las apariciones de X al inicio o
- Mover todas las apariciones de X al final.
Ejemplos:
Entrada: arr[] = {2, 1, 1, 2, 3, 1, 4, 3}, N = 8
Salida: 2
Explicación:
Primera operación -> Seleccione X = 1 y agregue todos los 1 al frente.
La array actualizada arr[] = {1, 1, 1, 2, 2, 3, 4, 3}.
Segunda operación -> Seleccione X= 4 y agregue todos los 4 al final.
La array actualizada arr[ ] = [1, 1, 1, 2, 2, 3, 3, 4].
Por lo tanto, la array se ordena en dos operaciones.Entrada: arr[] = {1, 1, 2, 2}, N = 4
Salida: 0
Explicación: La array ya está ordenada. Por lo tanto la respuesta es 0.
Enfoque: Este problema se puede resolver utilizando el enfoque codicioso basado en la siguiente idea.
La idea para resolver este problema es encontrar la subsecuencia más larga de elementos (considerando todas las ocurrencias de un elemento) que estarán en posiciones consecutivas en forma ordenada. Entonces, esos elementos no necesitan moverse a ningún otro lugar, y solo mover los otros elementos ordenará la array en pasos mínimos.
Siga la ilustración a continuación para una mejor comprensión:
Ilustración:
Por ejemplo arr[] = {2, 1, 1, 2, 3, 1, 4, 3} .
Cuando los elementos estén ordenados, serán {1, 1, 1, 2, 2, 3, 3, 4}.
La subsecuencia más larga en arr[] que está en posiciones consecutivas, ya que estarán en una array ordenada, es {2, 2, 3, 3}.Entonces, los elementos únicos restantes son solo {1, 4}.
Las operaciones mínimas requeridas son 2.Primera operación:
=> Mover todos los 1 al frente de la array.
=> La array actualizada arr[] = {1, 1, 1, 2, 2, 3, 4, 3}Segunda operación:
=> Mover 4 al final de la array.
=> La array actualizada arr[] = {1, 1, 1, 2, 2, 3, 3, 4}
Siga los pasos a continuación para resolver este problema basado en la idea anterior:
- Divide los elementos en tres categorías.
- Los elementos que vamos a mover al frente .
- Los elementos que no vamos a mover a ningún lado .
- Los elementos que moveremos al final .
- Entonces, para ordenar la array , estas tres condiciones deben cumplirse .
- Todos los elementos de la primera categoría deben ser menores que el elemento más pequeño de la segunda categoría .
- Todos los elementos de la tercera categoría deben ser mayores que el elemento más grande de la segunda categoría .
- Si eliminamos todos los elementos de la primera y tercera categoría, la array restante debe ordenarse en orden no decreciente.
- Entonces, para minimizar los pasos totales, los elementos de la segunda categoría deben ser máximos, como se ve en la idea anterior .
- Almacena la primera y la última aparición de cada elemento.
- Comience a iterar desde i = N a 1 (considere i como un elemento de array y no como un índice):
- Si su punto final es más pequeño que el índice inicial del elemento, un poco más grande que él, aumente el tamaño de la subsecuencia.
- Si no es así, configúrelo como el último y continúe con los demás elementos.
- Los elementos únicos que no sean los de la subsecuencia más larga es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum operation
// to sort the array
int minOpsSortArray(vector<int>& arr, int N)
{
vector<vector<int> > O(N + 1,
vector<int>(2, N + 1));
// Storing the first and the last occurrence
// of each integer.
for (int i = 0; i < N; ++i) {
O[arr[i]][0] = min(O[arr[i]][0], i);
O[arr[i]][1] = i;
}
int ans = 0, tot = 0;
int last = N + 1, ctr = 0;
for (int i = N; i > 0; i--) {
// Checking if the integer 'i'
// is present in the array or not.
if (O[i][0] != N + 1) {
ctr++;
// Checking if the last occurrence
// of integer 'i' comes before
// the first occurrence of the
// integer 'j' that is just greater
// than integer 'i'.
if (O[i][1] < last) {
tot++;
ans = max(ans, tot);
last = O[i][0];
}
else {
tot = 1;
last = O[i][0];
}
}
}
// Total number of distinct integers -
// maximum number of distinct integers
// that we do not move.
return ctr - ans;
}
// Driver code
int main()
{
int N = 8;
vector<int> arr = { 2, 1, 1, 2, 3, 1, 4, 3 };
// Function call
cout << minOpsSortArray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to find the minimum operation
// to sort the array
static int minOpsSortArray(int[] arr, int N)
{
int[][] O = new int[N + 1][N + 1];
for (int i = 0; i < N+1; i++) {
for (int j = 0; j < N+1; j++) {
O[i][j]=N+1;
}
}
// Storing the first and the last occurrence
// of each integer.
for (int i = 0; i < N; ++i) {
O[arr[i]][0] = Math.min(O[arr[i]][0], i);
O[arr[i]][1] = i;
}
int ans = 0, tot = 0;
int last = N + 1, ctr = 0;
for (int i = N; i > 0; i--) {
// Checking if the integer 'i'
// is present in the array or not.
if (O[i][0] != N + 1) {
ctr++;
// Checking if the last occurrence
// of integer 'i' comes before
// the first occurrence of the
// integer 'j' that is just greater
// than integer 'i'.
if (O[i][1] < last) {
tot++;
ans = Math.max(ans, tot);
last = O[i][0];
}
else {
tot = 1;
last = O[i][0];
}
}
}
// Total number of distinct integers -
// maximum number of distinct integers
// that we do not move.
return ctr - ans;
}
// Driver Code
public static void main (String[] args) {
int N = 8;
int[] arr = { 2, 1, 1, 2, 3, 1, 4, 3 };
// Function call
System.out.print(minOpsSortArray(arr, N));
}
}
// This code is contributed by code_hunt.
Python3
# Python3 code for the above approach # Function to find the minimum operation # to sort the array def minOpsSortArray(arr, N): O = [] for i in range(N + 1): O.append([N + 1, N + 1]) # Storing the first and last # occurrence of each integer for i in range(N): O[arr[i]][0] = min(O[arr[i]][0], i) O[arr[i]][1] = i ans = 0 tot = 0 last = N + 1 ctr = 0 for i in range(N, 0, -1): # Checking if the integer 'i' # is present in the array or not if O[i][0] != N + 1: ctr += 1 # Checking if the last occurrence # of integer 'i' comes before # the first occurrence of the # integer 'j' that is just greater # than integer 'i' if O[i][1] < last: tot += 1 ans = max(ans, tot) last = O[i][0] else: tot = 1 last = O[i][0] # total number of distinct integers # maximum number of distinct integers # that we do not move return ctr - ans # Driver Code N = 8 arr = [2, 1, 1, 2, 3, 1, 4, 3] # Function Call print(minOpsSortArray(arr, N)) # This code is contributed by phasing17
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum operation
// to sort the array
static int minOpsSortArray(int[] arr, int N)
{
int[,] O = new int[N + 1, N + 1];
for (int i = 0; i < N+1; i++) {
for (int j = 0; j < N+1; j++) {
O[i, j]=N+1;
}
}
// Storing the first and the last occurrence
// of each integer.
for (int i = 0; i < N; ++i) {
O[arr[i], 0] = Math.Min(O[arr[i], 0], i);
O[arr[i], 1] = i;
}
int ans = 0, tot = 0;
int last = N + 1, ctr = 0;
for (int i = N; i > 0; i--) {
// Checking if the integer 'i'
// is present in the array or not.
if (O[i, 0] != N + 1) {
ctr++;
// Checking if the last occurrence
// of integer 'i' comes before
// the first occurrence of the
// integer 'j' that is just greater
// than integer 'i'.
if (O[i, 1] < last) {
tot++;
ans = Math.Max(ans, tot);
last = O[i, 0];
}
else {
tot = 1;
last = O[i, 0];
}
}
}
// Total number of distinct integers -
// maximum number of distinct integers
// that we do not move.
return ctr - ans;
}
// Driver Code
public static void Main()
{
int N = 8;
int[] arr = { 2, 1, 1, 2, 3, 1, 4, 3 };
// Function call
Console.Write(minOpsSortArray(arr, N));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript code for above approach
// Function to find the minimum operation
// to sort the array
const minOpsSortArray = (arr, N) => {
let O = new Array(N + 1).fill(0).map(() => new Array(2).fill(N + 1));
// Storing the first and the last occurrence
// of each integer.
for (let i = 0; i < N; ++i) {
O[arr[i]][0] = Math.min(O[arr[i]][0], i);
O[arr[i]][1] = i;
}
let ans = 0, tot = 0;
let last = N + 1, ctr = 0;
for (let i = N; i > 0; i--) {
// Checking if the integer 'i'
// is present in the array or not.
if (O[i][0] != N + 1) {
ctr++;
// Checking if the last occurrence
// of integer 'i' comes before
// the first occurrence of the
// integer 'j' that is just greater
// than integer 'i'.
if (O[i][1] < last) {
tot++;
ans = Math.max(ans, tot);
last = O[i][0];
}
else {
tot = 1;
last = O[i][0];
}
}
}
// Total number of distinct integers -
// maximum number of distinct integers
// that we do not move.
return ctr - ans;
}
// Driver code
let N = 8;
let arr = [2, 1, 1, 2, 3, 1, 4, 3];
// Function call
document.write(minOpsSortArray(arr, N));
// This code is contributed by rakeshsahni
</script>
2
Complejidad temporal : O(N)
Espacio auxiliar: O(N)