Exemple de code pour résoudre le problème médian de deux listes ordonnées à l'aide de JavaScript

Disposez les nombres dans une séquence de petit à grand. À ce moment, la valeur de la variable au milieu est appelée la valeur médiane.

Alors, étant donné deux listes ordonnées, comment trouver leur médiane commune ?

Lorsque vous rencontrez ce problème, la première solution à laquelle vous pensez est de fusionner les deux listes ordonnées, puis de les trier par ordre croissant, et enfin de retirer la valeur médiane d'un coup.

Cette approche est très simple et pratique, mais elle n'est pas efficace à cause du tri, c'est donc un algorithme de O(N*logN).

Alors, comment optimiser ?

Vous pouvez vous référer à l'algorithme de fusion des listes linéaires ordonnées :

1 Utilisez deux pointeurs pour pointer vers la liste ordonnée actuelle et utilisez un nouveau tableau pour recevoir. la comparaison d'éléments de tableau plus petits.

2. Comparez les éléments du tableau pointés par les deux pointeurs, stockez le plus petit dans le nouveau tableau et déplacez le pointeur vers l'arrière. Ce processus se poursuivra jusqu'à ce que l'un des pointeurs soit vide ou que la valeur médiane ait été reçue par le nouveau tableau, puis la valeur médiane sera renvoyée directement.

3.Si après la phase 2 est terminée, un pointeur n'est pas nul et la valeur médiane n'est pas reçue par le nouveau tableau à ce moment, alors continuez à utiliser le pointeur pour parcourir la liste ordonnée, jusqu'à ce que la valeur médiane soit reçue, renvoyez-la.

4.L'algorithme optimisé est O(m n), et l'efficacité est grandement améliorée.

var findMedianSortedArrays = function(nums1, nums2) {
	//两个列表的总元素个数
    var totalLength = nums1.length + nums2.length;
	//总元素个数是否为奇数
    var isOdd = totalLength % 2 === 0 ? false : true;
	//两个指针
    var p1 = 0;
    var p2 = 0;
	//用于接收的新数组
    var array = [];
	//只要指针仍然在范围内
    while(p1 < nums1.length && p2 < nums2.length){
		//将较小的元素压入新数组，指针后移
        if(nums1[p1] < nums2[p2]){
            array.push(nums1[p1]);
            p1++;
        }
        else{
            array.push(nums2[p2]);
            p2++;
        }
		//如果此时已接收中值,弹出中值，返回
        if(array.length === totalLength / 2 + 1){
            return (array.pop() + array.pop()) / 2;
        }
        if(isOdd && array.length === Math.ceil(totalLength / 2)){
            return array.pop();
        }
    }
	//有一个指针已经出界了
	//此时仍然没有接收到中值
	//对另一个指针继续遍历
	//直到接收中值,弹出中值，并返回
    while(p1 < nums1.length){
        array.push(nums1[p1]);
        if(array.length === totalLength / 2 + 1){
            return (array.pop() + array.pop()) / 2;
        }
        if(isOdd && array.length === Math.ceil(totalLength / 2)){
            return array.pop();
        }
        p1++;
    }
    while(p2 < nums2.length){
        array.push(nums2[p2]);
        if(array.length === totalLength / 2 + 1){
            return (array.pop() + array.pop()) / 2;
        }
        if(isOdd && array.length === Math.ceil(totalLength / 2)){
            return array.pop();
        }
        p2++;
    }
};

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!