Dada una array de n enteros (se permiten duplicados). Escriba «Sí» si es un conjunto de enteros contiguos, de lo contrario, escriba «No».
Ejemplos:
Input : arr[] = {5, 2, 3, 6, 4, 4, 6, 6}
Output : Yes
The elements form a contiguous set of integers
which is {2, 3, 4, 5, 6}.
Input : arr[] = {10, 14, 10, 12, 12, 13, 15}
Output : No
Hemos discutido diferentes soluciones para distintos elementos en la siguiente publicación.
Comprobar si los elementos de la array son consecutivos
Una solución simple es ordenar primero la array. Luego recorra la array para verificar si todos los elementos consecutivos difieren como máximo en uno.
C
// Sorting based C++ implementation
// to check whether the array
// contains a set of contiguous
// integers
#include <bits/stdc++.h>
using namespace std;
// function to check whether
// the array contains a set
// of contiguous integers
bool areElementsContiguous(int arr[], int n)
{
// Sort the array
sort(arr, arr+n);
// After sorting, check if
// current element is either
// same as previous or is
// one more.
for (int i = 1; i < n; i++)
if (arr[i] - arr[i-1] > 1)
return false;
return true;
}
// Driver program to test above
int main()
{
int arr[] = { 5, 2, 3, 6,
4, 4, 6, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
if (areElementsContiguous(arr, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Sorting based Java implementation
// to check whether the array
// contains a set of contiguous
// integers
import java.util.*;
class GFG {
// function to check whether
// the array contains a set
// of contiguous integers
static boolean areElementsContiguous(int arr[],
int n)
{
// Sort the array
Arrays.sort(arr);
// After sorting, check if
// current element is either
// same as previous or is
// one more.
for (int i = 1; i < n; i++)
if (arr[i] - arr[i-1] > 1)
return false;
return true;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = { 5, 2, 3, 6,
4, 4, 6, 6 };
int n = arr.length;
if (areElementsContiguous(arr, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Sorting based Python implementation
# to check whether the array
# contains a set of contiguous integers
def areElementsContiguous(arr, n):
# Sort the array
arr.sort()
# After sorting, check if
# current element is either
# same as previous or is
# one more.
for i in range(1,n):
if (arr[i] - arr[i-1] > 1) :
return 0
return 1
# Driver code
arr = [ 5, 2, 3, 6, 4, 4, 6, 6 ]
n = len(arr)
if areElementsContiguous(arr, n): print("Yes")
else: print("No")
# This code is contributed by 'Ansu Kumari'.
C#
// Sorting based C# implementation
// to check whether the array
// contains a set of contiguous
// integers
using System;
class GFG {
// function to check whether
// the array contains a set
// of contiguous integers
static bool areElementsContiguous(int []arr,
int n)
{
// Sort the array
Array.Sort(arr);
// After sorting, check if
// current element is either
// same as previous or is
// one more.
for (int i = 1; i < n; i++)
if (arr[i] - arr[i - 1] > 1)
return false;
return true;
}
// Driver program
public static void Main()
{
int []arr = { 5, 2, 3, 6,
4, 4, 6, 6 };
int n = arr.Length;
if (areElementsContiguous(arr, n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Vt_m.
PHP
<?php
// Sorting based PHP implementation to check
// whether the array contains a set of contiguous
// integers
// function to check whether the array contains
// a set of contiguous integers
function areElementsContiguous($arr, $n)
{
// Sort the array
sort($arr);
// After sorting, check if current element
// is either same as previous or is one more.
for ($i = 1; $i < $n; $i++)
if ($arr[$i] - $arr[$i - 1] > 1)
return false;
return true;
}
// Driver Code
$arr = array( 5, 2, 3, 6,
4, 4, 6, 6 );
$n = sizeof($arr);
if (areElementsContiguous($arr, $n))
echo "Yes";
else
echo "No";
// This code is contributed by ajit
?>
Javascript
<script>
// Sorting based Javascript implementation
// to check whether the array
// contains a set of contiguous
// integers
// function to check whether
// the array contains a set
// of contiguous integers
function areElementsContiguous(arr, n)
{
// Sort the array
arr.sort(function(a, b){return a - b});
// After sorting, check if
// current element is either
// same as previous or is
// one more.
for (let i = 1; i < n; i++)
if (arr[i] - arr[i - 1] > 1)
return false;
return true;
}
let arr = [ 5, 2, 3, 6, 4, 4, 6, 6 ];
let n = arr.length;
if (areElementsContiguous(arr, n))
document.write("Yes");
else
document.write("No");
// This code is contributed by rameshtravel07.
</script>
Producción:
Yes
Complejidad de tiempo: O(n Log n)
Otro enfoque es: –
si podemos encontrar el elemento mínimo y el elemento máximo que están presentes en la array y usamos el siguiente procedimiento, entonces podemos decir que la array contiene elementos contiguos o no.
PROCEDIMIENTO :-
1) Almacene los elementos en un conjunto desordenado (para mantener la complejidad del tiempo del problema, es decir, O (n))
2) Encuentre el elemento mínimo presente en la array y guárdelo en una variable, digamos min_ele.
3) Encuentre el elemento máximo presente en la array y guárdelo en una variable, digamos max_ele.
4) Ahora solo piense un poco que podemos notar que si restamos el min_ele del max_ele y agregamos 1 al resultado.
5) Si el resultado final es igual al tamaño del conjunto, en ese caso podemos decir que la array dada contiene elementos contiguos.
Tomemos un ejemplo para entender el procedimiento anterior.
Digamos que después de almacenar el valor en el conjunto desordenado tenemos los valores dentro del 1 al 10 (1,2,3,4,5,6,7,8,9,10). El orden real dentro del conjunto no ordenado no es así. Lo acabo de tomar para una comprensión más fácil.
Del ejemplo anterior, podemos decir claramente que el elemento máximo presente en el conjunto es 10 y el elemento mínimo presente en el conjunto es 1.
Restando el elemento mínimo del elemento máximo obtenemos 9 como resultado (10-1=9).
Ahora, cuando agregamos 1 al resultado y lo comparamos con el tamaño del conjunto desordenado, podemos decir que son iguales. (9+1=10 que es igual al tamaño del conjunto desordenado).
Por lo tanto, la función devolverá True.
Ahora imagine si uno de los elementos no está presente en el conjunto desordenado (digamos 5), entonces en ese caso el tamaño del conjunto desordenado es 9, entonces en ese caso 10, que es el resultado final, no es igual al tamaño del conjunto desordenado. Y por lo tanto, la función devolverá False.
La implementación del método anterior es: –
C++
// C++ implementation to check whether the array contains a
// set of contiguous integers
#include <bits/stdc++.h>
using namespace std;
// function to check whether the array contains a set of
// contiguous integers
bool areElementsContiguous(int arr[], int n)
{
// Declaring and Initialising the set simultaneously
unordered_set<int> s(arr, arr + n);
// Finding the size of the unordered set
int set_size = s.size();
// Find maximum and minimum elements.
int max = *max_element(arr, arr + n);
int min = *min_element(arr, arr + n);
int result = max - min + 1;
if (result != set_size)
return false;
return true;
}
// Driver program
int main()
{
int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
if (areElementsContiguous(arr, n))
cout << "Yes";
else
cout << "No";
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// JAVA implementation to check whether the array contains a
// set of contiguous integers
import java.util.*;
class GFG {
// function to check whether the array contains a set of
// contiguous integers
public static boolean
areElementsContiguous(ArrayList<Integer> arr, int n)
{
// Declaring and Initialising the set simultaneously
HashSet<Integer> s = new HashSet<Integer>();
for (int i = 0; i < n; ++i)
s.add(arr.get(i));
// Finding the size of the unordered set
int set_size = s.size();
// Find maximum and minimum elements.
int max = Collections.max(arr);
int min = Collections.min(arr);
int result = max - min + 1;
if (result != set_size)
return false;
return true;
}
// Driver program
public static void main(String[] args)
{
ArrayList<Integer> arr = new ArrayList<Integer>(
Arrays.asList(5, 2, 3, 6, 4, 4, 6, 6));
int n = arr.size();
if (areElementsContiguous(arr, n))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by Taranpreet
Producción
Yes
COMPLEJIDAD DE TIEMPO :- O(n)
COMPLEJIDAD DEL ESPACIO :- O(n)
Solución eficiente utilizando array visitada
1) Encuentre los elementos mínimo y máximo.
2) Cree una array visitada de tamaño max-min + 1. Inicialice esta array como falsa.
3) Recorra la array dada y marque visited[arr[i] – min] como verdadero para cada elemento arr[i].
4) Atraviese la array visitada y devuelva verdadero si todos los valores son verdaderos. De lo contrario, devuelve falso.
C++
// C++ implementation to
// check whether the array
// contains a set of
// contiguous integers
#include <bits/stdc++.h>
using namespace std;
// function to check
// whether the array
// contains a set of
// contiguous integers
bool areElementsContiguous(int arr[], int n)
{
// Find maximum and
// minimum elements.
int max = *max_element(arr, arr + n);
int min = *min_element(arr, arr + n);
int m = max - min + 1;
// There should be at least
// m elements in array to
// make them contiguous.
if (m > n)
return false;
// Create a visited array
// and initialize false.
bool visited[m];
memset(visited, false, sizeof(visited));
// Mark elements as true.
for (int i=0; i<n; i++)
visited[arr[i] - min] = true;
// If any element is not
// marked, all elements
// are not contiguous.
for (int i=0; i<m; i++)
if (visited[i] == false)
return false;
return true;
}
// Driver program
int main()
{
int arr[] = { 5, 2, 3, 6,
4, 4, 6, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
if (areElementsContiguous(arr, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation to
// check whether the array
// contains a set of
// contiguous integers
import java.util.*;
class GFG {
// function to check
// whether the array
// contains a set of
// contiguous integers
static boolean areElementsContiguous(int arr[],
int n)
{
// Find maximum and
// minimum elements.
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < n; i++)
{
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
int m = max - min + 1;
// There should be at least
// m elements in array to
// make them contiguous.
if (m > n)
return false;
// Create a visited array
// and initialize false.
boolean visited[] = new boolean[n];
// Mark elements as true.
for (int i = 0; i < n; i++)
visited[arr[i] - min] = true;
// If any element is not
// marked, all elements
// are not contiguous.
for (int i = 0; i < m; i++)
if (visited[i] == false)
return false;
return true;
}
/* Driver program */
public static void main(String[] args)
{
int arr[] = { 5, 2, 3, 6,
4, 4, 6, 6 };
int n = arr.length;
if (areElementsContiguous(arr, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# Python3 implementation to
# check whether the array
# contains a set of
# contiguous integers
# function to check
# whether the array
# contains a set of
# contiguous integers
def areElementsContiguous(arr, n):
# Find maximum and
# minimum elements.
max1 = max(arr)
min1 = min(arr)
m = max1 - min1 + 1
# There should be at least
# m elements in array to
# make them contiguous.
if (m > n):
return False
# Create a visited array
# and initialize false
visited = [0] * m
# Mark elements as true.
for i in range(0,n) :
visited[arr[i] - min1] = True
# If any element is not
# marked, all elements
# are not contiguous.
for i in range(0, m):
if (visited[i] == False):
return False
return True
# Driver program
arr = [5, 2, 3, 6, 4, 4, 6, 6 ]
n = len(arr)
if (areElementsContiguous(arr, n)):
print("Yes")
else:
print("No")
# This code is contributed by Smitha Dinesh Semwal
C#
// C# implementation to check whether
// the array contains a set of
// contiguous integers
using System;
class GFG {
// function to check whether the
// array contains a set of
// contiguous integers
static bool areElementsContiguous(
int []arr, int n)
{
// Find maximum and
// minimum elements.
int max = int.MinValue;
int min = int.MaxValue;
for(int i = 0; i < n; i++)
{
max = Math.Max(max, arr[i]);
min = Math.Min(min, arr[i]);
}
int m = max - min + 1;
// There should be at least
// m elements in array to
// make them contiguous.
if (m > n)
return false;
// Create a visited array
// and initialize false.
bool []visited = new bool[n];
// Mark elements as true.
for (int i = 0; i < n; i++)
visited[arr[i] - min] = true;
// If any element is not
// marked, all elements
// are not contiguous.
for (int i = 0; i < m; i++)
if (visited[i] == false)
return false;
return true;
}
/* Driver program */
public static void Main()
{
int []arr = { 5, 2, 3, 6,
4, 4, 6, 6 };
int n = arr.Length;
if (areElementsContiguous(arr, n))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by nitin mittal.
Javascript
<script>
// Javascript implementation to
// check whether the array
// contains a set of
// contiguous integers
// function to check whether the
// array contains a set of
// contiguous integers
function areElementsContiguous(arr, n)
{
// Find maximum and
// minimum elements.
let max = Number.MIN_VALUE;
let min = Number.MAX_VALUE;
for(let i = 0; i < n; i++)
{
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
let m = max - min + 1;
// There should be at least
// m elements in array to
// make them contiguous.
if (m > n)
return false;
// Create a visited array
// and initialize false.
let visited = new Array(n);
visited.fill(false);
// Mark elements as true.
for (let i = 0; i < n; i++)
visited[arr[i] - min] = true;
// If any element is not
// marked, all elements
// are not contiguous.
for (let i = 0; i < m; i++)
if (visited[i] == false)
return false;
return true;
}
let arr = [ 5, 2, 3, 6, 4, 4, 6, 6 ];
let n = arr.length;
if (areElementsContiguous(arr, n))
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad de tiempo: O(n)
Solución eficiente usando la tabla hash
Inserta todos los elementos en la tabla hash. Ahora elija el primer elemento y siga incrementando su valor en 1 hasta que encuentre un valor que no esté presente en la tabla hash. Elija nuevamente el primer elemento y siga disminuyendo su valor en 1 hasta que encuentre un valor que no esté presente en la tabla hash. Obtenga el recuento de elementos (obtenidos por este proceso) que están presentes en la tabla hash. Si el recuento es igual al tamaño del hash, escriba «Sí», de lo contrario, «No».
C++
// C++ implementation to check whether the array
// contains a set of contiguous integers
#include <bits/stdc++.h>
using namespace std;
// Function to check whether the array contains
// a set of contiguous integers
bool areElementsContiguous(int arr[], int n)
{
// Storing elements of 'arr[]' in a hash
// table 'us'
unordered_set<int> us;
for (int i = 0; i < n; i++)
us.insert(arr[i]);
// as arr[0] is present in 'us'
int count = 1;
// starting with previous smaller element
// of arr[0]
int curr_ele = arr[0] - 1;
// if 'curr_ele' is present in 'us'
while (us.find(curr_ele) != us.end()) {
// increment count
count++;
// update 'curr_ele"
curr_ele--;
}
// starting with next greater element
// of arr[0]
curr_ele = arr[0] + 1;
// if 'curr_ele' is present in 'us'
while (us.find(curr_ele) != us.end()) {
// increment count
count++;
// update 'curr_ele"
curr_ele++;
}
// returns true if array contains a set of
// contiguous integers else returns false
return (count == (int)(us.size()));
}
// Driver program to test above
int main()
{
int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
if (areElementsContiguous(arr, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation to check whether the array
// contains a set of contiguous integers
import java.io.*;
import java.util.*;
class GFG {
// Function to check whether the array
// contains a set of contiguous integers
static Boolean areElementsContiguous(int arr[], int n)
{
// Storing elements of 'arr[]' in
// a hash table 'us'
HashSet<Integer> us = new HashSet<Integer>();
for (int i = 0; i < n; i++)
us.add(arr[i]);
// As arr[0] is present in 'us'
int count = 1;
// Starting with previous smaller
// element of arr[0]
int curr_ele = arr[0] - 1;
// If 'curr_ele' is present in 'us'
while (us.contains(curr_ele) == true) {
// increment count
count++;
// update 'curr_ele"
curr_ele--;
}
// Starting with next greater
// element of arr[0]
curr_ele = arr[0] + 1;
// If 'curr_ele' is present in 'us'
while (us.contains(curr_ele) == true) {
// increment count
count++;
// update 'curr_ele"
curr_ele++;
}
// Returns true if array contains a set of
// contiguous integers else returns false
return (count == (us.size()));
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 };
int n = arr.length;
if (areElementsContiguous(arr, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by 'Gitanjali'.
Python
# Python implementation to check whether the array
# contains a set of contiguous integers
# Function to check whether the array
# contains a set of contiguous integers
def areElementsContiguous(arr):
# Storing elements of 'arr[]' in a hash table 'us'
us = set()
for i in arr: us.add(i)
# As arr[0] is present in 'us'
count = 1
# Starting with previous smaller element of arr[0]
curr_ele = arr[0] - 1
# If 'curr_ele' is present in 'us'
while curr_ele in us:
# Increment count
count += 1
# Update 'curr_ele"
curr_ele -= 1
# Starting with next greater element of arr[0]
curr_ele = arr[0] + 1
# If 'curr_ele' is present in 'us'
while curr_ele in us:
# Increment count
count += 1
# Update 'curr_ele"
curr_ele += 1
# Returns true if array contains a set of
# contiguous integers else returns false
return (count == len(us))
# Driver code
arr = [ 5, 2, 3, 6, 4, 4, 6, 6 ]
if areElementsContiguous(arr): print("Yes")
else: print("No")
# This code is contributed by 'Ansu Kumari'
C#
using System;
using System.Collections.Generic;
// c# implementation to check whether the array
// contains a set of contiguous integers
public class GFG
{
// Function to check whether the array
// contains a set of contiguous integers
public static bool? areElementsContiguous(int[] arr, int n)
{
// Storing elements of 'arr[]' in
// a hash table 'us'
HashSet<int> us = new HashSet<int>();
for (int i = 0; i < n; i++)
{
us.Add(arr[i]);
}
// As arr[0] is present in 'us'
int count = 1;
// Starting with previous smaller
// element of arr[0]
int curr_ele = arr[0] - 1;
// If 'curr_ele' is present in 'us'
while (us.Contains(curr_ele) == true)
{
// increment count
count++;
// update 'curr_ele"
curr_ele--;
}
// Starting with next greater
// element of arr[0]
curr_ele = arr[0] + 1;
// If 'curr_ele' is present in 'us'
while (us.Contains(curr_ele) == true)
{
// increment count
count++;
// update 'curr_ele"
curr_ele++;
}
// Returns true if array contains a set of
// contiguous integers else returns false
return (count == (us.Count));
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = new int[] {5, 2, 3, 6, 4, 4, 6, 6};
int n = arr.Length;
if (areElementsContiguous(arr, n).Value)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript implementation to check whether the array
// contains a set of contiguous integers
// Function to check whether the array contains
// a set of contiguous integers
function areElementsContiguous(arr, n)
{
// Storing elements of 'arr[]' in a hash
// table 'us'
var us = new Set();
for (var i = 0; i < n; i++)
us.add(arr[i]);
// as arr[0] is present in 'us'
var count = 1;
// starting with previous smaller element
// of arr[0]
var curr_ele = arr[0] - 1;
// if 'curr_ele' is present in 'us'
while (us.has(curr_ele)) {
// increment count
count++;
// update 'curr_ele"
curr_ele--;
}
// starting with next greater element
// of arr[0]
curr_ele = arr[0] + 1;
// if 'curr_ele' is present in 'us'
while (us.has(curr_ele)) {
// increment count
count++;
// update 'curr_ele"
curr_ele++;
}
// returns true if array contains a set of
// contiguous integers else returns false
return (count == (us.size));
}
// Driver program to test above
var arr = [5, 2, 3, 6, 4, 4, 6, 6];
var n = arr.length;
if (areElementsContiguous(arr, n))
document.write( "Yes");
else
document.write( "No");
// This code is contributed by rutvik_56.
</script>
Producción :
Yes
Complejidad temporal: O(n).
Espacio Auxiliar: O(n).
Este método requiere solo un recorrido de la array dada. Recorre la tabla hash después del recorrido de la array (la tabla hash contiene solo elementos distintos).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA