es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • Tengo una cadena que necesito ordenar según un orden personalizado y estoy usando colas de prioridad, pero la cola de prioridad falla con duplicados.

Tengo una cadena que necesito ordenar según un orden personalizado y estoy usando colas de prioridad, pero la cola de prioridad falla con duplicados.

21 Jul, 2023 Programación

public class CustomSortString {

public String customSortString(String order, String s) {
    if (order == null || s == null) {
        return "";
    }
    int len = s.length();
    PriorityQueue<character> minHeap = new PriorityQueue<>(len, (a, b) -> {
        if (order.indexOf(a) > order.indexOf(b)) {
            return 1;
        } else if (order.indexOf(a) < order.indexOf(b)) {
            return -1;
        } else {
            return 0;
        }
    });
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < len; i++) {
        minHeap.add(s.charAt(i));
    }
    List<character> sortedList = new ArrayList<>();
    while (!minHeap.isEmpty()) {
        sortedList.add(minHeap.poll());
    }
    for (char c : sortedList) {
        result.append(c);
    }
    return result.toString();
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    CustomSortString c = new CustomSortString();
    System.out.println(c.customSortString("kqep", "pekeq"));
}

}

Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    El problema con el código está en el comparador de la PriorityQueue. La implementación actual asume que todos los caracteres en la cadena de orden son únicos, lo cual puede no ser siempre el caso. En las entradas “kqep” y “pekeq”, tanto “e” como “p” ocurren varias veces, lo que lleva a resultados impredecibles.

    Para solucionar esto, podemos modificar el comparador para verificar la igualdad antes de buscar el índice. Es decir, podemos cambiar la implementación a:

    PriorityQueue<character> minHeap = new PriorityQueue<>(len, (a, b) -> {
    int aIndex = order.indexOf(a);
    int bIndex = order.indexOf(b);
    if (aIndex == -1) {
        return bIndex == -1 ? 0 : 1; // a no está en orden, b está en orden: a > b
    } else if (bIndex == -1) {
        return -1; // b no está en orden, a está en orden: a < b
    } else {
        return Integer.compare(aIndex, bIndex); // ambos están en orden: comparar índice
    }
});

    Esta implementación primero verifica si alguno de los caracteres no está en la cadena de orden, en cuyo caso simplemente podemos comparar su existencia en la cadena de orden. De lo contrario, utilizamos el método compareTo para comparar los índices de los dos caracteres.

    Con esta modificación, el código debería producir la salida correcta para las entradas “kqep” y “pekeq”. ¡Espero que esto sea de ayuda!

Comments are closed.