Ordnen Sie die Zahlen in einer Reihenfolge von klein nach groß an. Zu diesem Zeitpunkt wird der Wert der Variablen in der Mitte als Medianwert bezeichnet.
Wie findet man also bei zwei gegebenen geordneten Listen ihren gemeinsamen Median?
Wenn dieses Problem auftritt, ist die erste Lösung, die Ihnen einfällt, die beiden geordneten Listen zusammenzuführen, sie dann in aufsteigender Reihenfolge zu sortieren und schließlich den Medianwert auf einmal zu ermitteln.
Dieser Ansatz ist sehr einfach und praktisch, aber aufgrund der Sortierung nicht effizient, daher handelt es sich um einen Algorithmus von O(N*logN).
Wie kann man also optimieren?
Sie können sich auf den Algorithmus zum Zusammenführen geordneter linearer Listen beziehen:
1. Verwenden Sie zwei Zeiger, um auf die aktuelle geordnete Liste zu zeigen, und verwenden Sie zum Empfangen ein neues Array der Vergleich kleinerer Array-Elemente.
2. Vergleichen Sie die Array-Elemente, auf die die beiden Zeiger zeigen, speichern Sie das kleinere im neuen Array und bewegen Sie den Zeiger nach hinten. Dieser Vorgang wird fortgesetzt, bis einer der Zeiger leer ist oder der Medianwert vom neuen Array empfangen wurde. Anschließend wird der Medianwert direkt zurückgegeben.
3.Wenn nach Abschluss von Phase 2 ein Zeiger ungleich Null ist und der Mittelwert zu diesem Zeitpunkt nicht vom neuen Array empfangen wird, fahren Sie mit der Verwendung fort Der Zeiger durchläuft die geordnete Liste, bis der Medianwert empfangen wird, und gibt ihn zurück.
4.Der optimierte Algorithmus ist O(m+n) und die Effizienz wird erheblich verbessert.
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++;
}
};Das obige ist der detaillierte Inhalt vonBeispielcode zur Lösung des Medianproblems zweier geordneter Listen mithilfe von JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
