242 lines
10 KiB
HTML
242 lines
10 KiB
HTML
|
<!DOCTYPE html>
|
|||
|
|
<html lang="zh-Hans">
|
|||
|
|
<head>
|
|||
|
|
<meta charset="UTF-8">
|
|||
|
|
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
|||
|
|
<title>068. 寻找两个正序数组的中位数 – 图解</title>
|
|||
|
|
<link rel="stylesheet" href="../shared/style.css">
|
|||
|
|
<style>
|
|||
|
|
.vis-area { min-height: 120px; padding: 16px 0; }
|
|||
|
|
.code-section { margin-top: 16px; }
|
|||
|
|
.cut-line { display:inline-block; width:3px; height:36px; background:var(--red); margin:0 2px; vertical-align:bottom; border-radius:2px; position:relative; }
|
|||
|
|
.cut-label { position:absolute; top:-16px; left:50%; transform:translateX(-50%); font-size:10px; color:var(--red); font-weight:700; white-space:nowrap; }
|
|||
|
|
.side-label { display:inline-block; padding:2px 8px; border-radius:6px; font-size:12px; font-weight:600; margin:0 4px; }
|
|||
|
|
.side-label.left-side { background:#dbeafe; color:#1e40af; }
|
|||
|
|
.side-label.right-side { background:#fef3c7; color:#92400e; }
|
|||
|
|
</style>
|
|||
|
|
</head>
|
|||
|
|
<body>
|
|||
|
|
<div class="container">
|
|||
|
|
<h1>🔴 068. 寻找两个正序数组的中位数 <span class="badge hard">困难</span></h1>
|
|||
|
|
<p class="subtitle">分类：二分查找 ｜ LeetCode Hot 100</p>
|
|||
|
|
|
|||
|
|
<div class="controls" id="controls">
|
|||
|
|
<label for="inputArea">输入：</label>
|
|||
|
|
<input type="text" id="inputArea" placeholder="nums1=[1,3], nums2=[2]">
|
|||
|
|
<button id="applyBtn" class="primary">生成图解</button>
|
|||
|
|
<select id="exampleSelect"></select>
|
|||
|
|
<span style="flex:1"></span>
|
|||
|
|
<button id="prevBtn">◀ 上一步</button>
|
|||
|
|
<button id="nextBtn">下一步 ▶</button>
|
|||
|
|
<button id="jumpBtn">⏭ 跳到结果</button>
|
|||
|
|
<button id="autoBtn">自动播放</button>
|
|||
|
|
<button id="resetBtn">重置</button>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<div class="pipeline" id="pipeline"></div>
|
|||
|
|
|
|||
|
|
<div class="hint info" id="hintBox">
|
|||
|
|
<span id="stepInfo"></span><br>
|
|||
|
|
<span id="hintText"></span>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<div class="panels">
|
|||
|
|
<div class="panel" id="mainPanel">
|
|||
|
|
<h3>📊 可视化</h3>
|
|||
|
|
<div class="vis-area" id="vizArea">点击「生成图解」开始</div>
|
|||
|
|
</div>
|
|||
|
|
<div class="panel-grid">
|
|||
|
|
<div class="panel" id="detailPanel">
|
|||
|
|
<h3>📝 当前步骤详情</h3>
|
|||
|
|
<div id="detailContent">等待开始...</div>
|
|||
|
|
</div>
|
|||
|
|
<div class="panel" id="resultPanel">
|
|||
|
|
<h3>✅ 结果</h3>
|
|||
|
|
<div id="resultContent">等待完成...</div>
|
|||
|
|
</div>
|
|||
|
|
</div>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<div class="panel code-section">
|
|||
|
|
<h3>💻 参考代码（Python）</h3>
|
|||
|
|
<div id="codeArea"></div>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<footer>Powered by QwenPaw · 图解算法 · LeetCode Hot 100</footer>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<script src="../shared/algo-viz.js"></script>
|
|||
|
|
<script>
|
|||
|
|
"use strict";
|
|||
|
|
(function() {
|
|||
|
|
const examples = [
|
|||
|
|
{nums1:[1,3], nums2:[2], label:'示例1: [1,3]+[2]'},
|
|||
|
|
{nums1:[1,2], nums2:[3,4], label:'示例2: [1,2]+[3,4]'},
|
|||
|
|
{nums1:[1], nums2:[2,3,4,5,6], label:'示例3: [1]+[2,3,4,5,6]'},
|
|||
|
|
{nums1:[], nums2:[1], label:'示例4: []+[1]'},
|
|||
|
|
];
|
|||
|
|
let A, B, steps, stepCtrl;
|
|||
|
|
|
|||
|
|
function buildSteps(a, b) {
|
|||
|
|
// Ensure A is the shorter array
|
|||
|
|
if (a.length > b.length) { [a, b] = [b, a]; }
|
|||
|
|
A = a; B = b;
|
|||
|
|
steps = [];
|
|||
|
|
|
|||
|
|
const m = a.length, n = b.length;
|
|||
|
|
const halfLen = Math.floor((m + n + 1) / 2);
|
|||
|
|
steps.push({stage:'init', msg:`确保较短的数组为A（长度${m}），较长为B（长度${n}），halfLen = ⌊(${m}+${n}+1)/2⌋ = ${halfLen}`, iLeft:0, iRight:m, iA:-1, iB:-1, leftMax:null, rightMin:null, valid:false});
|
|||
|
|
|
|||
|
|
let iLeft = 0, iRight = m;
|
|||
|
|
while (iLeft <= iRight) {
|
|||
|
|
const iA = Math.floor((iLeft + iRight) / 2);
|
|||
|
|
const iB = halfLen - iA;
|
|||
|
|
|
|||
|
|
const Aleft = iA > 0 ? a[iA - 1] : -Infinity;
|
|||
|
|
const Aright = iA < m ? a[iA] : Infinity;
|
|||
|
|
const Bleft = iB > 0 ? b[iB - 1] : -Infinity;
|
|||
|
|
const Bright = iB < n ? b[iB] : Infinity;
|
|||
|
|
|
|||
|
|
steps.push({stage:'calc', msg:`iA=${iA}, iB=${iB} → A_left=${Aleft}, A_right=${Aright}, B_left=${Bleft}, B_right=${Bright}`,
|
|||
|
|
iLeft, iRight, iA, iB, Aleft, Aright, Bleft, Bright, leftMax:null, rightMin:null, valid:false});
|
|||
|
|
|
|||
|
|
if (Aleft <= Bright && Bleft <= Aright) {
|
|||
|
|
const leftMax = Math.max(Aleft, Bleft);
|
|||
|
|
const rightMin = Math.min(Aright, Bright);
|
|||
|
|
steps.push({stage:'found', msg:`A_left(${Aleft}) ≤ B_right(${Bright}) ✓ 且 B_left(${Bleft}) ≤ A_right(${Aright}) ✓ → 切割有效！`,
|
|||
|
|
iLeft, iRight, iA, iB, Aleft, Aright, Bleft, Bright, leftMax, rightMin, valid:true});
|
|||
|
|
return;
|
|||
|
|
} else if (Aleft > Bright) {
|
|||
|
|
steps.push({stage:'goLeft', msg:`A_left(${Aleft}) > B_right(${Bright})，A的切割太靠右，iRight = ${iA}-1 = ${iA-1}`,
|
|||
|
|
iLeft, iRight:iA-1, iA, iB, Aleft, Aright, Bleft, Bright, leftMax:null, rightMin:null, valid:false});
|
|||
|
|
iRight = iA - 1;
|
|||
|
|
} else {
|
|||
|
|
steps.push({stage:'goRight', msg:`B_left(${Bleft}) > A_right(${Aright})，A的切割太靠左，iLeft = ${iA}+1 = ${iA+1}`,
|
|||
|
|
iLeft:iA+1, iRight, iA, iB, Aleft, Aright, Bleft, Bright, leftMax:null, rightMin:null, valid:false});
|
|||
|
|
iLeft = iA + 1;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function renderCutArray(arr, cutIdx, label) {
|
|||
|
|
// Use renderArray from shared lib for the base display, then overlay cut info
|
|||
|
|
if (arr.length === 0) return `<div style="margin:8px 0;"><b>${label}:</b> [空]</div>`;
|
|||
|
|
const hl = {};
|
|||
|
|
for (let i = 0; i < cutIdx; i++) hl[i] = 'blue';
|
|||
|
|
for (let i = cutIdx; i < arr.length; i++) hl[i] = 'orange';
|
|||
|
|
let html = `<div style="margin:8px 0;"><b>${label}:</b> `;
|
|||
|
|
html += renderArray(arr, {highlights: hl});
|
|||
|
|
if (cutIdx > 0 && cutIdx <= arr.length) {
|
|||
|
|
html += `<span style="color:var(--red);font-weight:700;font-size:12px;margin-left:4px;">↑ cut at ${cutIdx}</span>`;
|
|||
|
|
}
|
|||
|
|
html += '</div>';
|
|||
|
|
return html;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function render(step) {
|
|||
|
|
const s = steps[step];
|
|||
|
|
let viz = '';
|
|||
|
|
|
|||
|
|
viz += renderCutArray(A, s.iA >= 0 ? s.iA : 0, 'A (较短)');
|
|||
|
|
viz += renderCutArray(B, s.iB >= 0 ? s.iB : 0, 'B (较长)');
|
|||
|
|
|
|||
|
|
if (s.Aleft !== undefined) {
|
|||
|
|
viz += `<div style="margin-top:10px;">`;
|
|||
|
|
viz += `<span class="side-label left-side">左侧: A[${s.iA-1}]=${s.Aleft}, B[${s.iB-1}]=${s.Bleft}</span>`;
|
|||
|
|
viz += `<span class="side-label right-side">右侧: A[${s.iA}]=${s.Aright}, B[${s.iB}]=${s.Bright}</span>`;
|
|||
|
|
viz += `</div>`;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
if (s.valid) {
|
|||
|
|
const totalLen = A.length + B.length;
|
|||
|
|
const isOdd = totalLen % 2 === 1;
|
|||
|
|
const median = isOdd ? s.leftMax : (s.leftMax + s.rightMin) / 2;
|
|||
|
|
viz += `<div class="current-answer">✅ 切割有效！left_max = ${s.leftMax}, right_min = ${s.rightMin}<br>中位数 = ${median}</div>`;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
viz += `<div style="margin-top:6px;font-size:13px;color:var(--text-secondary);">iA = ${s.iA} iB = ${s.iB} 搜索范围: [${s.iLeft}..${s.iRight}]</div>`;
|
|||
|
|
|
|||
|
|
$('vizArea').innerHTML = viz;
|
|||
|
|
$('detailContent').innerHTML = `<div class="calc-block">${s.msg}</div>`;
|
|||
|
|
|
|||
|
|
if (s.valid) {
|
|||
|
|
const totalLen = A.length + B.length;
|
|||
|
|
const isOdd = totalLen % 2 === 1;
|
|||
|
|
const median = isOdd ? s.leftMax : (s.leftMax + s.rightMin) / 2;
|
|||
|
|
$('resultContent').innerHTML = `<div class="final-answer">中位数 = <b>${median}</b><br>
|
|||
|
|
总长度 ${totalLen}（${isOdd?'奇数':'偶数'}）<br>
|
|||
|
|
${isOdd ? `left_max = ${s.leftMax}` : `(left_max + right_min) / 2 = (${s.leftMax} + ${s.rightMin}) / 2 = ${median}`}<br>
|
|||
|
|
时间复杂度 O(log(min(m,n)))</div>`;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
$('hintText').textContent = s.msg;
|
|||
|
|
const stages = ['init→初始化','calc→计算切割','goLeft→左缩','goRight→右缩','found→找到'];
|
|||
|
|
$('pipeline').innerHTML = stages.map(st => {
|
|||
|
|
const [k,l] = st.split('→');
|
|||
|
|
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
|||
|
|
}).join('<i>→</i>');
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function init() {
|
|||
|
|
const sel = $('exampleSelect');
|
|||
|
|
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
|||
|
|
$('inputArea').value = 'nums1=[1,3], nums2=[2]';
|
|||
|
|
|
|||
|
|
buildSteps(examples[0].nums1, examples[0].nums2);
|
|||
|
|
stepCtrl = new StepController({onStep: render});
|
|||
|
|
stepCtrl.setSteps(steps.map((_,i)=>i));
|
|||
|
|
$('stepInfo').textContent = `步骤 1 / ${steps.length}`;
|
|||
|
|
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
|||
|
|
|
|||
|
|
$('applyBtn').onclick = () => {
|
|||
|
|
try {
|
|||
|
|
const m = $('inputArea').value.match(/nums1=\[([^\]]*)\].*nums2=\[([^\]]*)\]/);
|
|||
|
|
if (!m) { alert('格式: nums1=[1,3], nums2=[2]'); return; }
|
|||
|
|
const a = m[1] ? m[1].split(',').map(Number) : [];
|
|||
|
|
const b = m[2] ? m[2].split(',').map(Number) : [];
|
|||
|
|
buildSteps(a, b);
|
|||
|
|
stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
|||
|
|
$('stepInfo').textContent = `步骤 1 / ${steps.length}`;
|
|||
|
|
} catch(e) { alert('输入格式错误'); }
|
|||
|
|
};
|
|||
|
|
$('exampleSelect').onchange = () => {
|
|||
|
|
const e = examples[parseInt($('exampleSelect').value)];
|
|||
|
|
$('inputArea').value = `nums1=[${e.nums1}], nums2=[${e.nums2}]`;
|
|||
|
|
buildSteps(e.nums1, e.nums2);
|
|||
|
|
stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
|||
|
|
};
|
|||
|
|
$('prevBtn').onclick = () => stepCtrl.prev();
|
|||
|
|
$('nextBtn').onclick = () => stepCtrl.next();
|
|||
|
|
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
|||
|
|
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
|||
|
|
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
|||
|
|
}
|
|||
|
|
init();
|
|||
|
|
|
|||
|
|
$('codeArea').innerHTML = renderCode(`def findMedianSortedArrays(nums1, nums2):
|
|||
|
|
# 确保 A 是较短的数组
|
|||
|
|
if len(nums1) > len(nums2):
|
|||
|
|
nums1, nums2 = nums2, nums1
|
|||
|
|
m, n = len(nums1), len(nums2)
|
|||
|
|
half = (m + n + 1) // 2
|
|||
|
|
l, r = 0, m
|
|||
|
|
while l <= r:
|
|||
|
|
i = (l + r) // 2
|
|||
|
|
j = half - i
|
|||
|
|
Aleft = nums1[i-1] if i > 0 else float('-inf')
|
|||
|
|
Aright = nums1[i] if i < m else float('inf')
|
|||
|
|
Bleft = nums2[j-1] if j > 0 else float('-inf')
|
|||
|
|
Bright = nums2[j] if j < n else float('inf')
|
|||
|
|
if Aleft <= Bright and Bleft <= Aright:
|
|||
|
|
if (m + n) % 2:
|
|||
|
|
return max(Aleft, Bleft)
|
|||
|
|
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
|
|||
|
|
elif Aleft > Bright:
|
|||
|
|
r = i - 1
|
|||
|
|
else:
|
|||
|
|
l = i + 1`, {lang:'Python'});
|
|||
|
|
})();
|
|||
|
|
</script>
|
|||
|
|
</body>
|
|||
|
|
</html>
|