Encuentra todos los rangos de números consecutivos de Array

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>
Producción: 

[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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *