Minimice las eliminaciones requeridas para hacer una array dada consecutiva en cualquier orden

Dada una array arr[] . La tarea es minimizar el número de eliminaciones para que todos los elementos de arr[] sean consecutivos. 

Ejemplos

Entrada: arr[] = {45, 42, 46, 48, 47}
Salida: 1
Explicación: Después de eliminar 42 vemos que hay elementos consecutivos presentes en la array (45-48).

Entrada: arr[] = {7, 4, 8, 5, 9 }
Salida: 2
Explicación: Después de eliminar 4 y 5, vemos que hay elementos consecutivos presentes en la array (7-9).

Enfoque: este problema se puede resolver utilizando Hashmaps . Siga los pasos a continuación para resolver el problema dado. 

• En primer lugar, cree un mapa y en cada elemento, es decir, en cada tecla, ponga su valor verdadero .
• Entonces cada elemento/clave tiene un valor verdadero . Ahora muévase a través del conjunto de claves del mapa y vea si contiene (clave-1) en el mapa.
• Si se pone falso en esa tecla.
• Ahora, en otro ciclo, trabaje para las claves cuyo valor sea verdadero y vaya hasta su secuencia más larga y encuentre la longitud de la secuencia consecutiva más larga.
• Entonces, el número mínimo de eliminaciones será la diferencia en la longitud de la array y la longitud de la secuencia consecutiva más larga.

Siga los pasos a continuación para resolver el problema dado.

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
void minRemovalsConsecutive(vector<int>& a, int n)
{
 
  // Hashmap to store the elements
  // in key-value pairs
  map<int, bool> map;
 
  for (int val : a) {
    map[val] = true;
  }
  for (auto it = map.begin(); it != map.end(); ++it) {
    if (map.count(it->first - 1)) {
      map[it->first] = false;
    }
  }
  int max = 0;
 
  // Iterating for all keys in map
  for (auto it = map.begin(); it != map.end(); ++it) {
    if (map.count(it->first)) {
      int t1 = 1;
      while (map.count(it->first + t1)) {
        t1++;
      }
      if (t1 > max) {
        max = t1;
      }
    }
  }
 
  // Printing the final answer
  cout << (n - max);
}
 
// Driver Code
int main()
{
  int N = 5;
  vector<int> arr = { 45, 42, 46, 48, 47 };
 
  // Function Call
  minRemovalsConsecutive(arr, N);
 
  return 0;
}
 
// This code is contributed by rakeshsahni

// Java program for above approach
import java.io.*;
import java.util.*;
class GFG {
 
    public static void
    minRemovalsConsecutive(int a[], int n)
    {
        // Hashmap to store the elements
        // in key-value pairs
        HashMap<Integer, Boolean> map
            = new HashMap<>();
        for (int val : a) {
            map.put(val, true);
        }
        for (int val : map.keySet()) {
            if (map.containsKey(val - 1)) {
                map.put(val, false);
            }
        }
        int max = 0;
 
        // Iterating for all keys in map
        for (int val : map.keySet()) {
            if (map.get(val)) {
                int t1 = 1;
                while (map.containsKey(val
                                       + t1)) {
                    t1++;
                }
                if (t1 > max) {
                    max = t1;
                }
            }
        }
 
        // Printing the final answer
        System.out.println(n - max);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 5;
        int arr[] = { 45, 42, 46, 48, 47 };
 
        // Function Call
        minRemovalsConsecutive(arr, N);
    }
}

# Python 3 program for above approach
def minRemovalsConsecutive(a, n):
 
    # Hashmap to store the elements
    # in key-value pairs
    map = {}
 
    for val in a:
        map[val] = True
 
    for it in map:
        if ((it-1) in map):
            map[it] = False
    max = 0
 
    # Iterating for all keys in map
    for it in map:
        if (it in map):
            t1 = 1
            while ((it + t1) in map):
                t1 += 1
 
            if (t1 > max):
                max = t1
    # Printing the final answer
    print(n - max)
 
 
# Driver Code
if __name__ == "__main__":
    N = 5
    arr = [45, 42, 46, 48, 47]
 
    # Function Call
    minRemovalsConsecutive(arr, N)
 
    # This code is contributed by ukasp.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG {
 
  static void minRemovalsConsecutive(int []a, int n)
  {
     
    // Hashmap to store the elements
    // in key-value pairs
    Dictionary<int, bool> map1 =
      new Dictionary<int, bool>();
 
    foreach (int val in a) {
      map1.Add(val, true);
    }
 
    Dictionary<int, bool> map2 =
      new Dictionary<int, bool>();
 
    foreach(KeyValuePair<int, bool> k in map1){
      if (map1.ContainsKey(k.Key - 1)) {
        map2.Add(k.Key, false);
      }
      else {
        map2.Add(k.Key, true);
      }
    }
    int max = 0;
 
    // Iterating for all keys in map
    foreach(KeyValuePair<int, bool> k in map2){
      if (map2.ContainsKey(k.Key)) {
        int t1 = 1;
        while (map2.ContainsKey(k.Key
                                + t1)) {
          t1++;
        }
        if (t1 > max) {
          max = t1;
        }
      }
    }
 
    // Printing the final answer
    Console.WriteLine(n - max);
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 5;
    int []arr = { 45, 42, 46, 48, 47 };
 
    // Function Call
    minRemovalsConsecutive(arr, N);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
// Javascript program for above approach
function minRemovalsConsecutive(a, n) {
 
    // Hashmap to store the elements
    // in key-value pairs
    let map = new Map();
 
    for (val of a) {
        map.set(val, true);
    }
    for (let it of map.keys()) {
        if (map.has(it - 1)) {
            map.set(it, false);
        }
    }
    let max = 0;
 
    // Iterating for all keys in map
    for (val of map.keys()) {
        if (map.get(val)) {
            let t1 = 1;
            while (map.has(val + t1)) {
                t1++;
            }
            if (t1 > max) {
                max = t1;
            }
        }
    }
 
    // Printing the final answer
    document.write((n - max));
}
 
// Driver Code
 
let N = 5;
let arr = [45, 42, 46, 48, 47];
 
// Function Call
minRemovalsConsecutive(arr, N);
 
// This code is contributed by gfgking
</script>

1

Complejidad temporal: O(N)
Espacio auxiliar: O(N)