2948. Faites le plus petit tableau lexicographique en échangeant des éléments

Difficulté: moyen

Sujets: Array, Union Find, Tri

On vous donne un tableau 0 indexé de entiers positifs nums et une limite entière positive.

Dans une opération, vous pouvez choisir deux indices I et J et échanger nums [i] et nums [j] si | nums [i] - nums [j] | & lt; = limite.

return le le plus petit tableau lexicographique qui peut être obtenu en effectuant l'opération n'importe quel nombre de fois .

Un tableau A est lexicographiquement plus petit qu'un tableau B Si dans la première position où A et B diffèrent, le tableau A a un élément qui est inférieur à l'élément correspondant en b. Par exemple, le tableau [2,10,3] est lexicographiquement plus petit que le tableau [10,2,3] car ils diffèrent à l'indice 0 et 2 & lt; 10.

Exemple 1:

• Entrée: nums = [1,5,3,9,8], limite = 2
• Sortie: [1,3,5,8,9]
• Explication: Appliquer l'opération 2 fois:
  • Swap nums [1] avec nums [2]. Le tableau devient [1,3,5,9,8]
  • Swap nums [3] avec NUMS [4]. Le tableau devient [1,3,5,8,9]
  • Nous ne pouvons pas obtenir un tableau lexicographiquement plus petit en appliquant d'autres opérations.
  • Notez qu'il peut être possible d'obtenir le même résultat en effectuant différentes opérations.

Exemple 2:

• Entrée: nums = [1,7,6,18,2,1], limite = 3
• Sortie: [1,6,7,18,1,2]
• Explication: Appliquer l'opération 3 fois:
  • Swap nums [1] avec nums [2]. Le tableau devient [1,6,7,18,2,1]
  • Swap nums [0] avec nums [4]. Le tableau devient [2,6,7,18,1,1]
  • Swap nums [0] avec nums [5]. Le tableau devient [1,6,7,18,1,2]
  • Nous ne pouvons pas obtenir un tableau lexicographiquement plus petit en appliquant d'autres opérations.

Exemple 3:

• Entrée: nums = [1,7,28,19,10], limite = 3
• Sortie: [1,7,28,19,10]
• Explication: [1,7,28,19,10] est le plus petit tableau lexicographique que nous pouvons obtenir car nous ne pouvons pas appliquer l'opération sur deux indices.

Exemple 4:

• Entrée: nums = [1,60,34,84,62,56,39,76,49,38], limite = 4
• Sortie: [1,56,34,84,60,62,38,76,49,39]

Contraintes:

• 1 & lt; = nums.length & lt; = 10 ⁵
• 1 & lt; = nums [i] & lt; = 10 ⁹
• 1 & lt; = limite & lt; = 10 ⁹

Indice:

1. Construisez un graphique virtuel où tous les éléments en nombres sont des n?uds et les paires satisfaisant la condition ont un bord entre elles.
2. Au lieu de construire tous les bords, nous ne nous soucions que des composants connectés.
3. Pouvons-nous utiliser DSU?
4. Triez les numéros. Maintenant, nous devons simplement considérer si les éléments consécutifs ont un avantage pour vérifier s'ils appartiennent au même composant connecté. Par conséquent, tous les composants connectés deviennent une liste d'éléments consécutifs en position après le tri.
5. Pour chaque index de nums de 0 à nums.length - 1, nous pouvons le changer en valeur minimale actuelle que nous avons dans son composant connecté et supprimer cette valeur du composant connecté.

Solution:

Le problème nous demande de trouver le plus petit tableau lexicographique le plus petit en échangeant des éléments d'un tableau, sous réserve d'une condition. Plus précisément, nous ne pouvons échanger deux éléments nums [i] et nums [j] si la différence absolue entre eux (| nums [i] - nums [j] |) est inférieure ou égale à une limite donnée.

points clés

1. Ordre lexicographique : Un tableau a est lexicographiquement plus petit que B si au premier indice différent, a [i] & lt; b [i].
2. Condition d'échange : Les échanges ne sont autorisés que si la différence entre les nombres échangés est ≤ limite.
3. Groupement efficace : En utilisant Disjoint Set Union (DSU) ou des techniques de tri, nous pouvons regrouper des éléments connectés par des swaps valides.
4. Arrangement optimal : Pour chaque groupe, triez les indices et les valeurs pour réaliser le plus petit ordre.

Approche

1. Construire des groupes : Traitez le tableau comme un graphique virtuel, où les échanges valides définissent les bords. Utilisez le tri pour identifier efficacement les groupes connectés ou DSU aux indices de groupe.
2. Trier les groupes : Dans chaque groupe d'indices connectés, réorganisez les éléments de l'ordre lexicographique.
3. Construction de sortie : Remettez les valeurs triées dans leurs positions respectives.

plan

1. Extraire (valeur, index) les paires et les trier par valeur pour permettre une détection efficace de groupe.
2. itérer à travers des valeurs triées pour former des groupes d'indices connectés en fonction de la condition limite.
3. pour chaque groupe:
   • Trier les indices et valeurs indépendamment.
   • réaffecter les valeurs à leurs positions d'origine dans l'ordre lexicographique.
4. Renvoie le tableau modifié.

implémentons cette solution dans PHP: 2948. Faites le plus petit tableau lexicographique en échangeant des éléments

<?php
/**
 * @param Integer[] $nums
 * @param Integer $limit
 * @return Integer[]
 */
function lexicographicallySmallestArray($nums, $limit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $nums
 * @return array
 */
function getNumAndIndexes($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = [1, 5, 3, 9, 8];
$limit1 = 2;
print_r(lexicographicallySmallestArray($nums1, $limit1)); // Output: [1, 3, 5, 8, 9]

$nums2 = [1, 7, 6, 18, 2, 1];
$limit2 = 3;
print_r(lexicographicallySmallestArray($nums2, $limit2)); // Output: [1, 6, 7, 18, 1, 2]

$nums3 = [1, 7, 28, 19, 10];
$limit3 = 3;
print_r(lexicographicallySmallestArray($nums3, $limit3)); // Output: [1, 7, 28, 19, 10]

$nums4 = [1, 60, 34, 84, 62, 56, 39, 76, 49, 38];
$limit4 = 4;
print_r(lexicographicallySmallestArray($nums4, $limit4)); // Output: [1, 56, 34, 84, 60, 62, 38, 76, 49, 39]
?>

Explication:

1. Extraction et tri (getNumandIndexes):

   • Combinez les valeurs et les indices en paires pour une référence facile.
   • Triez les paires par valeur pour permettre un regroupement efficace des composants connectés.

2. Logique de regroupement?:

   • Parcourez les paires triées. Si la différence entre les valeurs consécutives est ≤ limite, ajoutez-les au même groupe?; sinon, créez un nouveau groupe.

3. Tri et réaffectation?:

   • Pour chaque groupe?:
     • Extraire les indices et les valeurs.
     • Triez les deux listes pour vous assurer que les plus petites valeurs sont placées dans les plus petits indices.
     • Réaffectez les valeurs triées à leurs positions respectives dans le tableau de réponses.

4. Construction des résultats?:

   • Après avoir traité tous les groupes, renvoyez le tableau mis à jour.

Exemple de procédure pas à pas

Exemple 1

Entrée?: nums = [1,5,3,9,8], limite = 2

1. Extraire et trier?:

   • Paires?: [(1, 0), (5, 1), (3, 2), (9, 3), (8, 4)]
   • Paires triées?: [(1, 0), (3, 2), (5, 1), (8, 4), (9, 3)]

2. Regroupement?:

   • Groupe 1?: [(1, 0)]
   • Groupe 2?: [(3, 2), (5, 1)]
   • Groupe 3?: [(8, 4), (9, 3)]

3. Tri des groupes?:

   • Groupe 1?: Aucun changement ([1])
   • Groupe 2 : Valeurs = [3, 5], Indices = [1, 2] → Résultat : [1, 3, 5]
   • Groupe 3 : Valeurs = [8, 9], Indices = [3, 4] → Résultat : [8, 9]

4. Résultat final?: [1, 3, 5, 8, 9]

Complexité temporelle

1. Tri?: Le tri du tableau nums prend O(n log n).
2. Regroupement?: Le parcours linéaire à travers le tableau trié prend O(n).
3. Tri des groupes?: Le tri des indices et des valeurs pour chaque groupe prend O(k log k), où k est la taille du groupe. Sommé sur tous les groupes, c'est O(n log n).

Complexité temporelle globale?: O(n log n)

Sortie pour exemples

Exemple 2

Entrée?: nums = [1,7,6,18,2,1], limite = 3

Sortie?: [1,6,7,18,1,2]

Exemple 3

Entrée?: nums = [1,7,28,19,10], limite = 3

Sortie?: [1,7,28,19,10]

Cette approche gère efficacement le problème en utilisant le tri pour identifier les composants connectés et en réorganisant les valeurs au sein de chaque composant pour obtenir le tableau lexicographiquement le plus petit. En tirant parti du tri et du traitement de groupe, nous garantissons une solution optimale avec une complexité O(n log n).

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre?:

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!