Dada una array arr[] de N enteros y un entero positivo K , la tarea es verificar si es posible dividir la array en subsecuencias crecientes de K enteros consecutivos, de modo que cada elemento pueda contribuir en una única subsecuencia.
Ejemplo :
Entrada: arr[] = {1, 2, 1, 3, 2, 3}, K = 3
Salida: Sí
Explicación: La array dada se puede dividir como { 1 , 2 , 1, 3 , 2, 3} => {1, 2, 3} y {1, 2, 1 , 3, 2 , 3 } => {1, 2, 3}. Ambas subsecuencias tienen 3 enteros consecutivos en orden creciente.Entrada: arr[] = {4, 3, 1, 2}, K = 2
Salida: No
Enfoque: el problema anterior se puede resolver utilizando un enfoque codicioso mediante la búsqueda binaria . Se puede observar que para cualquier entero arr[i] , la opción más óptima es elegir el índice más pequeño de arr[i] + 1 en el subarreglo arr[i+1, N) . Usando esta observación, siga los pasos a continuación para resolver el problema dado:
- Si K no es un divisor de N , no existe ningún conjunto posible de subsecuencias requeridas. Por lo tanto , imprima No.
- Almacene los índices de cada entero en una estructura de datos Set . Se puede almacenar de manera eficiente utilizando un mapa que tiene la estructura de un par de conjuntos de claves.
- Mantenga una array visitada para realizar un seguimiento de los índices que ya están incluidos en una subsecuencia.
- Iterar para cada i en el rango [0, N) , y si el número entero en el índice actual aún no se ha visitado, realice los siguientes pasos:
- Usando la función upper_bound , encuentre el índice más pequeño de arr[i] + 1 en el rango [i+1, N) y actualice el valor del último elemento de la subsecuencia actual con él.
- Repita el paso K-1 mencionado anteriormente varias veces hasta que se haya creado una subsecuencia completa de K enteros.
- Durante cualquier iteración, si el entero requerido no existe, no existe ningún conjunto posible de subsecuencias requeridas. Por lo tanto , imprima No. De lo contrario, imprima Sí .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the array can
// be divided into subsequences of K
// consecutive integers in increasing order
bool isPossible(vector<int> nums, int K)
{
int N = nums.size();
// If N is not divisible by K or
// K>N, no possible set of required
// subsequences exist
if (N % K != 0 || K > N) {
return false;
}
// Stores the indices of each
// element in a set
map<int, set<int> > idx;
// Stores the index of each number
for (int i = 0; i < nums.size(); i++) {
idx[nums[i]].insert(i);
}
// Stores if the integer at current
// index is already included in
// a subsequence
int visited[N] = { 0 };
// Stores the count of total
// visited elements
int total_visited = 0;
for (int i = 0; i < nums.size(); i++) {
// If current integer is already
// in a subsequence
if (visited[i]) {
continue;
}
// Stores the value of last element
// of the current subsequence
int num = nums[i];
// Stores the index of last element
// of the current subsequence
int last_index = i;
// Mark Visited
visited[i] = 1;
// Increment the visited count
total_visited++;
// Find the next K-1 elements of the
// subsequence starting from index i
for (int j = num + 1; j < num + K; j++) {
// No valid index found
if (idx[j].size() == 0) {
return false;
}
// Find index of j such that it
// is greater than last_index
auto it = idx[j].upper_bound(last_index);
// if no such index found,
// return false
if (it == idx[j].end()
|| *it <= last_index) {
return false;
}
// Update last_index
last_index = *it;
// Mark current index as visited
visited[last_index] = 1;
// Increment total_visited by 1
total_visited++;
// Remove the index from set because
// it has been already used
idx[j].erase(it);
}
}
// Return the result
return total_visited == N;
}
// Driver Code
int main()
{
vector<int> arr = { 4, 3, 1, 2 };
int K = 2;
cout << (isPossible(arr, K) ? "Yes" : "No");
return 0;
}
Python3
# Python3 program for the above approach
# Function to check if the array can
# be divided into subsequences of K
# consecutive integers in increasing order
def isPossible(nums, K):
N = len(nums)
# If N is not divisible by K or
# K>N, no possible set of required
# subsequences exist
if (N % K != 0 or K > N):
return False
# Stores the indices of each
# element in a set
idx = {}
# Stores the index of each number
for i in range(N):
if nums[i] in idx:
idx[nums[i]].add(i)
else:
idx[nums[i]] = {i}
# Stores if the integer at current
# index is already included in
# a subsequence
visited = [0]*N
# Stores the count of total
# visited elements
total_visited = 0
for i in range(N):
# If current integer is already
# in a subsequence
if(visited[i]):
continue
# Stores the value of last element
# of the current subsequence
num = nums[i]
# Stores the index of last element
# of the current subsequence
last_index = i
# Marked visited
visited[i] = 1
# Increment the visited count
total_visited += 1
# Find the next K-1 elements of the
# subsequence starting from index i
for j in range(num+1, num+K):
# No valid index found
if j not in idx or len(idx[j]) == 0:
return False
temp = False
# Find index of j such that it
# is greater than last_index
for it in idx[j]:
if it > last_index:
last_index = it
temp = True
break
if(temp == False):
return False
# Update last index
visited[last_index] = 1
# Mark current index as visited
# Increment total_visited by 1
total_visited += 1
# Remove the index
idx[j].remove(it)
# Return the result
return total_visited == N
# Driver code
arr = [4, 3, 1, 2]
K = 2
if (isPossible(arr, K)):
print("Yes")
else:
print("No")
# This code is contributed by parthmanchanda81
Javascript
<script>
// JavaScript program for the above approach
// Function to check if the array can
// be divided into subsequences of K
// consecutive integers in increasing order
function isPossible(nums, K){
let N = nums.length
// If N is not divisible by K or
// K>N, no possible set of required
// subsequences exist
if (N % K != 0 || K > N)
return false
// Stores the indices of each
// element in a set
let idx = new Map()
// Stores the index of each number
for(let i = 0; i < N; i++){
if(idx.has(nums[i]))
idx.get(nums[i]).add(i)
else{
idx.set(nums[i],new Set())
idx.get(nums[i]).add(i)
}
}
// Stores if the integer at current
// index is already included in
// a subsequence
let visited = new Array(N).fill(0)
// Stores the count of total
// visited elements
total_visited = 0
for(let i=0;i<N;i++){
// If current integer is already
// in a subsequence
if(visited[i])
continue
// Stores the value of last element
// of the current subsequence
let num = nums[i]
// Stores the index of last element
// of the current subsequence
let last_index = i
// Marked visited
visited[i] = 1
// Increment the visited count
total_visited += 1
// Find the next K-1 elements of the
// subsequence starting from index i
for(let j=num+1;j<num+K;j++){
// No valid index found
if(idx.has(j) == false || idx[j].length == 0)
return false
temp = false
// Find index of j such that it
// is greater than last_index
for(let it of idx[j]){
if(it > last_index){
last_index = it
temp = true
break
}
if(temp == false)
return false
}
// Update last index
visited[last_index] = 1
// Mark current index as visited
// Increment total_visited by 1
total_visited += 1
// Remove the index
idx[j].delete(it)
// Return the result
}
}
return (total_visited == N)
}
// Driver code
let arr = [4, 3, 1, 2]
let K = 2
if (isPossible(arr, K))
document.write("Yes","</br>")
else
document.write("No","</br>")
// This code is contributed by shinjanpatra
</script>
Producción:
No
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA