Divida la array dada en un número mínimo de subarreglos de modo que reorganizar el orden de los subarreglos ordene la array

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

Deja una respuesta

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