Início / coding / Perguntas / 79490590
Accepted
CodeCrusader
Asked: 2025-03-07 04:17:07 +0800 CST

operações mínimas para encontrar a ordem de classificação

  • 772

A descrição da tarefa é:

Tenho uma matriz de números distintos de 1 a n, por exemplo arr = [5, 3, 4, 1, 2]

Inicialize uma variável chamada order para 1, agora percorra o arr da esquerda para a direita e procure o elemento que corresponde à variável order, se encontrado incremente order e siga em frente. Em outras palavras, podemos dizer Inicialize uma variável chamada order para 1, então primeiro percorra o array da esquerda para a direita e veja onde 1 aparece no array, então incremente order para 2, então siga em frente no array e procure por 2, se encontrado incremente order para 3. Iterar da esquerda para a direita como acima é chamado de operação

para quando arr = [5,3,4,1,2], em uma passagem da esquerda para a direita, a ordem muda seu valor de 1 para 2 quando arr[3] é encontrado e então de 2 para 3 quando arr[4] é encontrado

Repita os passos acima até que a ordem da variável atinja o valor n. O número de repetições é chamado de operações.

Então quando arr [ 5,3,4,1,2], o número mínimo de operações necessárias é 3

import java.util.*;

class Main {
    public static int solve(List<Integer> arr) {
        int n = arr.size();
        int order = 0; // Number of sorted items found
        int operations = 0;  // Count of full array scan
        
        while (sortedCount < n) {
            order++;
            for (int i = 0; i < n; i++) {
                if (arr.get(i) == order + 1) {
                    order++;
                }
            }
        }        
        return operations;
    }

    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(5, 3, 4, 1, 2))); // Output: 3
        System.out.println(solve(Arrays.asList(3,1,4,2,5))); // Output: 2
        System.out.println(solve(Arrays.asList(1,2,3,4))); // Output: 1
        System.out.println(solve(Arrays.asList(2,1))); // Output: 2
    }
}

Meu código funciona em tempo O(n^2), como podemos resolver isso em menos complexidade de tempo

java

3 respostas

  1. Best Answer

    O algoritmo a seguir resolve o problema em O(n):

    public static int solve(List<Integer> arr) {
    int operations = 0;
    Set<Integer> visited = new HashSet<>();
    for (int i : arr) {
        if (!visited.contains(i - 1))
           operations++;
        visited.add(i);
    }
    return operations;
}

    A ideia é que se você não viu o número - 1 antes, então você tem que obtê-lo na próxima passagem, então isso está contando todas as passagens necessárias. Você poderia usar um array booleano em vez do conjunto hash para ter mais desempenho, mas é a mesma complexidade.

    • 3

  2. aqui está minha ideia

        public static int solve(List<Integer> arr) {
        int n = arr.size();
        Map<Integer, Integer> indexMap = new HashMap<>();
        
       
        for (int i = 0; i < n; i++) {
            indexMap.put(arr.get(i), i);
        }
        // we store
        //5 -> 0  
        //3 -> 1  
        //4 -> 2  
        //1 -> 3  
        //2 -> 4  
        
        int operations = 1; //we start from 1
        for (int i = 2; i <= n; i++) { // and try to find each next number (2, 3, 4, ...).
            //If index of i is bigger than index of (i - 1), we’re still good, Numbers are appearing in increasing order
            if (indexMap.get(i) < indexMap.get(i - 1)) {
                operations++; //BUT if index of i is smaller, that means we gotta restart our search (new operation needed).
            }
        }
        //One loop to build the map (O(n))
        //One loop to count operations (O(n))
        // => Total: O(n)
        return operations;
    }
    • 1

  3. Se a matriz contiver os números de 1 a N, você poderá simplesmente imprimir os números de 1 a N na ordem de classificação desejada, sem olhar para a matriz.

    • -3

relate perguntas