Dada una array arr[] que consta de N enteros, la tarea es encontrar el número mínimo de división de elementos de la array en subarreglos de modo que reorganizar el orden de los subarreglos ordene la array dada .
Ejemplos:
Entrada: arr[] = {6, 3, 4, 2, 1}
Salida: 4
Explicación:
La array dada se puede dividir en 4 subarreglos como {6}, {3, 4}, {2}, {1} y estos subarreglos se pueden reorganizar como {1}, {2}, {3, 4}, {6}. La array resultante será {1, 2, 3, 4, 6} que está ordenada. Por lo tanto, los subarreglos mínimos que se pueden dividir en la array dada para ordenar la array son 4.Entrada: arr[] = {1, -4, 0, -2}
Salida: 4
Enfoque: El problema dado se puede resolver manteniendo una versión ordenada de la array arr[] y agrupando todos los enteros en la array original que aparecen en la misma secuencia que en la array ordenada. A continuación se muestran los pasos:
- Mantenga un vector del par V que almacene el valor del elemento actual y el índice del elemento actual de la array arr[] para todos los elementos de la array dada.
- Ordenar el vector V .
- Inicialice una variable, digamos cnt como 1 que almacene la cantidad mínima de subarreglos requeridos.
- Recorra el vector V para i en el rango [1, N – 1] y realice los siguientes pasos:
- Si el índice del i -ésimo elemento en el arreglo original es (1 + índice del (i – 1) -ésimo elemento) en el arreglo original, entonces los dos pueden agruparse en el mismo subarreglo.
- De lo contrario, los dos elementos deben estar en subarreglos separados e incrementar el valor de cnt en 1 .
- Después de completar los pasos anteriores, imprima el valor de cnt como la posible ruptura resultante de subarreglos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to find minimum number of
// subarrays such that rearranging the
// subarrays sort the array
int numberOfSubarrays(int arr[], int n)
{
// Stores the minimum number of
// subarrays
int cnt = 1;
// Stores all the elements in the
// array with their indices
vector<pair<int, int> > v(n);
// Copy array elements in vector
for (int i = 0; i < n; i++) {
v[i].first = arr[i];
v[i].second = i;
}
// Sort the vector v
sort(v.begin(), v.end());
// Iterate through vector v
for (int i = 1; i < n; i++) {
// If the (i)th and (i-1)th element
// can be grouped in same subarray
if (v[i].second == v[i - 1].second + 1) {
continue;
}
else {
cnt++;
}
}
// Return resultant count
return cnt;
}
// Driver Code
int main()
{
int arr[] = { 6, 3, 4, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << numberOfSubarrays(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find minimum number of
// subarrays such that rearranging the
// subarrays sort the array
static int numberOfSubarrays(int arr[], int n)
{
// Stores the minimum number of
// subarrays
int cnt = 1;
// Stores all the elements in the
// array with their indices
pair[] v = new pair[n];
// Copy array elements in vector
for (int i = 0; i < n; i++) {
v[i] = new pair(0,0);
v[i].first = arr[i];
v[i].second = i;
}
// Sort the vector v
Arrays.sort(v,(a,b)->a.first-b.first);
// Iterate through vector v
for (int i = 1; i < n; i++) {
// If the (i)th and (i-1)th element
// can be grouped in same subarray
if (v[i].second == v[i - 1].second + 1) {
continue;
}
else {
cnt++;
}
}
// Return resultant count
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 6, 3, 4, 2, 1 };
int N = arr.length;
System.out.print(numberOfSubarrays(arr, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python Program to implement
# the above approach
# Function to find minimum number of
# subarrays such that rearranging the
# subarrays sort the array
def numberOfSubarrays(arr, n):
# Stores the minimum number of
# subarrays
cnt = 1
# Stores all the elements in the
# array with their indices
v = []
# Copy array elements in vector
for i in range(n):
v.append({'first': arr[i], 'second': i})
# Sort the vector v
v = sorted(v, key = lambda i: i['first'])
# Iterate through vector v
for i in range(1, n):
# If the (i)th and (i-1)th element
# can be grouped in same subarray
if (v[i]['second'] == v[i - 1]['second']+1):
continue
else:
cnt += 1
# Return resultant count
return cnt
# Driver Code
arr = [6, 3, 4, 2, 1]
N = len(arr)
print(numberOfSubarrays(arr, N))
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
class pair : IComparable<pair>
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
public int CompareTo(pair other)
{
// return other.Salary.CompareTo(this.Salary);
if (this.first < other.first)
{
return 1;
}
else if (this.first > other.first)
{
return -1;
}
else
{
return 0;
}
}
}
// Function to find minimum number of
// subarrays such that rearranging the
// subarrays sort the array
static int numberOfSubarrays(int []arr, int n)
{
// Stores the minimum number of
// subarrays
int cnt = 1;
// Stores all the elements in the
// array with their indices
pair[] v = new pair[n];
// Copy array elements in vector
for (int i = 0; i < n; i++) {
v[i] = new pair(0,0);
v[i].first = arr[i];
v[i].second = i;
}
// Sort the vector v
Array.Sort(v);
// Iterate through vector v
for (int i = 1; i < n; i++) {
// If the (i)th and (i-1)th element
// can be grouped in same subarray
if (v[i].second == v[i - 1].second + 1) {
continue;
}
else {
cnt++;
}
}
// Return resultant count
return cnt;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 6, 3, 4, 2, 1 };
int N = arr.Length;
Console.Write(numberOfSubarrays(arr, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find minimum number of
// subarrays such that rearranging the
// subarrays sort the array
function numberOfSubarrays(arr, n) {
// Stores the minimum number of
// subarrays
let cnt = 1;
// Stores all the elements in the
// array with their indices
let v = [];
// Copy array elements in vector
for (let i = 0; i < n; i++) {
v.push({ first: arr[i], second: i })
}
// Sort the vector v
v.sort(function (a, b) { return a.first - b.first })
// Iterate through vector v
for (let i = 1; i < n; i++) {
// If the (i)th and (i-1)th element
// can be grouped in same subarray
if (v[i].second == v[i - 1].second + 1) {
continue;
}
else {
cnt++;
}
}
// Return resultant count
return cnt;
}
// Driver Code
let arr = [6, 3, 4, 2, 1];
let N = arr.length;
document.write(numberOfSubarrays(arr, N));
// This code is contributed by Potta Lokesh
</script>
Producción
4
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por krishnumkhodke y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA