Dada una array de enteros. La tarea es encontrar el número mínimo de secuencias consecutivas que se pueden formar usando los elementos de la array.
Ejemplos:
Input: arr[] = { -3, -2, -1, 0, 2 } Output: 2 Consecutive sequences are (-3, -2, -1, 0), (2). Input: arr[] = { 3, 4, 0, 2, 6, 5, 10 } Output: 3 Consecutive sequences are (0), {2, 3, 4, 5, 6} and {10}
Acercarse:
- Ordenar la array.
- Repita la array y verifique si el elemento actual es solo 1 más pequeño que el siguiente elemento.
- Si es así, incremente el conteo en 1.
- Devuelve el recuento final de secuencias consecutivas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program find the minimum number of consecutive // sequences in an array #include <bits/stdc++.h> using namespace std; int countSequences(int arr[], int n) { int count = 1; sort(arr, arr + n); for (int i = 0; i < n - 1; i++) if (arr[i] + 1 != arr[i + 1]) count++; return count; } // Driver program int main() { int arr[] = { 1, 7, 3, 5, 10 }; int n = sizeof(arr) / sizeof(arr[0]); // function call to print required answer cout << countSequences(arr, n); return 0; }
Java
// Java program find the minimum number of consecutive // sequences in an array import java.util.Arrays; import java.io.*; class GFG { static int countSequences(int arr[], int n) { int count = 1; Arrays.sort(arr); for (int i = 0; i < n - 1; i++) if (arr[i] + 1 != arr[i + 1]) count++; return count; } // Driver program public static void main (String[] args) { int arr[] = { 1, 7, 3, 5, 10 }; int n = arr.length; // function call to print required answer System.out.println( countSequences(arr, n)); } //This code is contributed by ajit. }
Python3
# Python3 program find the minimum number of consecutive # sequences in an array def countSequences(arr, n) : count = 1 arr.sort() for i in range( n -1) : if (arr[i] + 1 != arr[i + 1]) : count += 1 return count # Driver program if __name__ == "__main__" : arr = [ 1, 7, 3, 5, 10 ] n = len(arr) # function call to print required answer print(countSequences(arr, n)) # This code is contributed by Ryuga
C#
// C# program find the minimum number of consecutive // sequences in an array using System; class GFG { static int countSequences(int []arr, int n) { int count = 1; Array.Sort(arr); for (int i = 0; i < n - 1; i++) if (arr[i] + 1 != arr[i + 1]) count++; return count; } // Driver program static public void Main (String []args) { int []arr = { 1, 7, 3, 5, 10 }; int n = arr.Length; // function call to print required answer Console.WriteLine( countSequences(arr, n)); } } //This code is contributed by Arnab Kundu
PHP
<?php // PHP program find the minimum number // of consecutive sequences in an array function countSequences($arr, $n) { $count = 1; sort($arr); for ($i = 0; $i < $n - 1; $i++) if ($arr[$i] + 1 != $arr[$i + 1]) $count++; return $count; } // Driver Code $arr = array( 1, 7, 3, 5, 10 ); $n = count($arr); // function call to print required answer echo countSequences($arr, $n); // This code is contributed by inder_verma ?>
Javascript
<script> // Javascript program find the // minimum number of consecutive // sequences in an array function countSequences(arr, n) { let count = 1; arr.sort(function(a, b){return a - b}); for (let i = 0; i < n - 1; i++) if (arr[i] + 1 != arr[i + 1]) count++; return count; } let arr = [ 1, 7, 3, 5, 10 ]; let n = arr.length; // function call to print required answer document.write(countSequences(arr, n)); </script>
Producción:
5
Complejidad de tiempo: O (n log n), donde n es el tamaño de la array.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA