Dada una array ordenada arr[] que consta de N enteros sin duplicados, la tarea es encontrar los rangos de números consecutivos de esa array.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 6, 7}
Salida: 1->3, 6->7
Explicación:
Hay dos rangos de números consecutivos de esa array.
Rango 1 = 1 -> 3
Rango 2 = 6 -> 7
Entrada: arr[] = {-1, 0, 1, 2, 5, 6, 8}
Salida: -1->2, 5->6, 8
Explicación:
Hay tres rangos de números consecutivos de esa array.
Rango 1 = -1 -> 2
Rango 2 = 5 -> 6
Rango 3 = 8
Enfoque: la idea es atravesar la array desde la posición inicial y, para cada elemento de la array, verificar la diferencia entre el elemento actual y el elemento anterior.
- Si la diferencia entre el elemento actual y el elemento anterior es 1, simplemente incrementamos la variable de longitud. Usamos la variable de longitud para construir el rango «A -> B» . Dado que solo se requiere el rango, no necesitamos almacenar todos los elementos entre A y B. Solo necesitamos saber la longitud de este rango.
- Si la diferencia entre el elemento actual y el elemento anterior no es igual a 1, construimos el rango entre el primer elemento del rango y el elemento anterior actual como el último rango.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the ranges of // consecutive numbers from array #include<bits/stdc++.h> using namespace std; // Function to find consecutive ranges vector<string> consecutiveRanges(int a[], int n) { int length = 1; vector<string> list; // If the array is empty, // return the list if (n == 0) { return list; } // Traverse the array from first position for(int i = 1; i <= n; i++) { // Check the difference between the // current and the previous elements // If the difference doesn't equal to 1 // just increment the length variable. if (i == n || a[i] - a[i - 1] != 1) { // If the range contains // only one element. // add it into the list. if (length == 1) { list.push_back(to_string(a[i - length])); } else { // Build the range between the first // element of the range and the // current previous element as the // last range. string temp = to_string(a[i - length]) + " -> " + to_string(a[i - 1]); list.push_back(temp); } // After finding the first range // initialize the length by 1 to // build the next range. length = 1; } else { length++; } } return list; } // Driver Code. int main() { // Test Case 1: int arr1[] = { 1, 2, 3, 6, 7 }; int n = sizeof(arr1) / sizeof(arr1[0]); vector<string> ans = consecutiveRanges(arr1, n); cout << "["; for(int i = 0; i < ans.size(); i++) { if(i == ans.size() - 1) cout << ans[i] << "]" << endl; else cout << ans[i] << ", "; } // Test Case 2: int arr2[] = { -1, 0, 1, 2, 5, 6, 8 }; n = sizeof(arr2) / sizeof(arr2[0]); ans = consecutiveRanges(arr2, n); cout << "["; for(int i = 0; i < ans.size(); i++) { if(i == ans.size() - 1) cout << ans[i] << "]" << endl; else cout << ans[i] << ", "; } // Test Case 3: int arr3[] = { -1, 3, 4, 5, 20, 21, 25 }; n = sizeof(arr3) / sizeof(arr3[0]); ans = consecutiveRanges(arr3, n); cout << "["; for(int i = 0; i < ans.size(); i++) { if(i == ans.size() - 1) cout << ans[i] << "]" << endl; else cout << ans[i] << ", "; } } // This code is contributed by Surendra_Gangwar
Java
// Java program to find the ranges of // consecutive numbers from array import java.util.*; class GFG { // Function to find consecutive ranges static List<String> consecutiveRanges(int[] a) { int length = 1; List<String> list = new ArrayList<String>(); // If the array is empty, // return the list if (a.length == 0) { return list; } // Traverse the array from first position for (int i = 1; i <= a.length; i++) { // Check the difference between the // current and the previous elements // If the difference doesn't equal to 1 // just increment the length variable. if (i == a.length || a[i] - a[i - 1] != 1) { // If the range contains // only one element. // add it into the list. if (length == 1) { list.add( String.valueOf(a[i - length])); } else { // Build the range between the first // element of the range and the // current previous element as the // last range. list.add(a[i - length] + " -> " + a[i - 1]); } // After finding the first range // initialize the length by 1 to // build the next range. length = 1; } else { length++; } } return list; } // Driver Code. public static void main(String args[]) { // Test Case 1: int[] arr1 = { 1, 2, 3, 6, 7 }; System.out.print(consecutiveRanges(arr1)); System.out.println(); // Test Case 2: int[] arr2 = { -1, 0, 1, 2, 5, 6, 8 }; System.out.print(consecutiveRanges(arr2)); System.out.println(); // Test Case 3: int[] arr3 = { -1, 3, 4, 5, 20, 21, 25 }; System.out.print(consecutiveRanges(arr3)); } }
Python3
# Python3 program to find # the ranges of consecutive # numbers from array # Function to find # consecutive ranges def consecutiveRanges(a, n): length = 1 list = [] # If the array is empty, # return the list if (n == 0): return list # Traverse the array # from first position for i in range (1, n + 1): # Check the difference # between the current # and the previous elements # If the difference doesn't # equal to 1 just increment # the length variable. if (i == n or a[i] - a[i - 1] != 1): # If the range contains # only one element. # add it into the list. if (length == 1): list.append(str(a[i - length])) else: # Build the range between the first # element of the range and the # current previous element as the # last range. temp = (str(a[i - length]) + " -> " + str(a[i - 1])) list.append(temp) # After finding the # first range initialize # the length by 1 to # build the next range. length = 1 else: length += 1 return list # Driver Code. if __name__ == "__main__": # Test Case 1: arr1 = [1, 2, 3, 6, 7] n = len(arr1) ans = consecutiveRanges(arr1, n) print ("[", end = "") for i in range(len(ans)): if(i == len(ans) - 1): print (ans[i], "]") else: print (ans[i], end = ", ") # Test Case 2: arr2 = [-1, 0, 1, 2, 5, 6, 8] n = len(arr2) ans = consecutiveRanges(arr2, n) print ("[", end = "") for i in range (len(ans)): if(i == len(ans) - 1): print (ans[i], "]") else: print (ans[i], end = ", ") # Test Case 3: arr3 = [-1, 3, 4, 5, 20, 21, 25] n = len(arr3) ans = consecutiveRanges(arr3, n) print ("[", end = "") for i in range (len(ans)): if(i == len(ans) - 1): print (ans[i], "]") else: print (ans[i], end = ", ") # This code is contributed by Chitranayal
C#
// C# program to find the ranges of // consecutive numbers from array using System; using System.Collections.Generic; class GFG{ // Function to find consecutive ranges static List<String> consecutiveRanges(int[] a) { int length = 1; List<String> list = new List<String>(); // If the array is empty, // return the list if (a.Length == 0) { return list; } // Traverse the array from first position for(int i = 1; i <= a.Length; i++) { // Check the difference between the // current and the previous elements // If the difference doesn't equal to 1 // just increment the length variable. if (i == a.Length || a[i] - a[i - 1] != 1) { // If the range contains // only one element. // add it into the list. if (length == 1) { list.Add( String.Join("", a[i - length])); } else { // Build the range between the first // element of the range and the // current previous element as the // last range. list.Add(a[i - length] + " -> " + a[i - 1]); } // After finding the first range // initialize the length by 1 to // build the next range. length = 1; } else { length++; } } return list; } static void print(List<String> arr) { Console.Write("["); foreach(String i in arr) Console.Write(i + ", "); Console.Write("]"); } // Driver Code. public static void Main(String []args) { // Test Case 1: int[] arr1 = { 1, 2, 3, 6, 7 }; print(consecutiveRanges(arr1)); Console.WriteLine(); // Test Case 2: int[] arr2 = { -1, 0, 1, 2, 5, 6, 8 }; print(consecutiveRanges(arr2)); Console.WriteLine(); // Test Case 3: int[] arr3 = { -1, 3, 4, 5, 20, 21, 25 }; print(consecutiveRanges(arr3)); } } // This code is contributed by Amit Katiyar
Javascript
<script> // JavaScript program to find the ranges of // consecutive numbers from array // Function to find consecutive ranges function consecutiveRanges(a) { let length = 1; let list = []; // If the array is empty, // return the list if (a.length == 0) { return list; } // Traverse the array from first position for (let i = 1; i <= a.length; i++) { // Check the difference between the // current and the previous elements // If the difference doesn't equal to 1 // just increment the length variable. if (i == a.length || a[i] - a[i - 1] != 1) { // If the range contains // only one element. // add it into the list. if (length == 1) { list.push( (a[i - length]).toString()); } else { // Build the range between the first // element of the range and the // current previous element as the // last range. list.push(a[i - length] + " -> " + a[i - 1]); } // After finding the first range // initialize the length by 1 to // build the next range. length = 1; } else { length++; } } return list; } // Driver Code. // Test Case 1: let arr1=[ 1, 2, 3, 6, 7]; document.write("["); document.write(consecutiveRanges(arr1)); document.write("]"); document.write("<br>"); // Test Case 2: let arr2=[ -1, 0, 1, 2, 5, 6, 8 ]; document.write("["); document.write(consecutiveRanges(arr2)); document.write("]"); document.write("<br>"); // Test Case 3: let arr3=[ -1, 3, 4, 5, 20, 21, 25 ]; document.write("["); document.write(consecutiveRanges(arr3)); document.write("]"); // This code is contributed by avanitrachhadiya2155 </script>
[1 -> 3, 6 -> 7] [-1 -> 2, 5 -> 6, 8] [-1, 3 -> 5, 20 -> 21, 25]
Complejidad de tiempo: O(N) , donde N es la longitud de la array.
Publicación traducida automáticamente
Artículo escrito por prashant_srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA