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