310 lines
12 KiB
HTML
310 lines
12 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>017. 缺失的第一个正数 – 图解</title>
|
||
<link rel="stylesheet" href="../shared/style.css">
|
||
<style>
|
||
.vis-area { min-height: 200px; padding: 16px 0; }
|
||
.code-section { margin-top: 16px; }
|
||
.target-row { display: flex; gap: 0; margin: 4px 0; align-items: center; }
|
||
.target-cell {
|
||
min-width: 40px; height: 24px; display: flex; align-items: center; justify-content: center;
|
||
font-size: 11px; font-weight: 600; color: #64748b; font-family: monospace;
|
||
}
|
||
.swap-arrow {
|
||
font-size: 18px; color: #f59e0b; margin: 0 4px; font-weight: 700;
|
||
animation: swapPulse 0.6s ease infinite alternate;
|
||
}
|
||
@keyframes swapPulse { from { opacity: 0.5; } to { opacity: 1; } }
|
||
.pos-tag {
|
||
display: inline-block; padding: 2px 8px; border-radius: 6px; font-size: 12px;
|
||
font-weight: 600; margin: 2px;
|
||
}
|
||
.pos-tag.correct { background: #dcfce7; color: #166534; }
|
||
.pos-tag.wrong { background: #fee2e2; color: #991b1b; }
|
||
.pos-tag.scanning { background: #fef3c7; color: #92400e; }
|
||
.pos-tag.missing { background: #ede9fe; color: #5b21b6; box-shadow: 0 0 0 2px #8b5cf6; }
|
||
.slot-label {
|
||
font-size: 11px; color: #94a3b8; text-align: center; margin-top: 2px;
|
||
}
|
||
</style>
|
||
</head>
|
||
<body>
|
||
<div class="container">
|
||
<h1>🔴 017. 缺失的第一个正数 <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="默认示例，可自定义">
|
||
<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 = [
|
||
{input:[3,4,-1,1], label:'示例1: [3,4,-1,1]'},
|
||
{input:[1,2,0], label:'示例2: [1,2,0]'},
|
||
{input:[7,8,9,11,12], label:'示例3: [7,8,9,11,12]'},
|
||
{input:[1,1], label:'重复: [1,1]'},
|
||
{input:[2,1], label:'交换: [2,1]'},
|
||
];
|
||
let nums, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
nums = [...arr];
|
||
steps = [];
|
||
const n = nums.length;
|
||
const a = [...arr]; // working copy
|
||
|
||
// Init
|
||
steps.push({
|
||
stage:'init', arr:[...a], swapFrom:-1, swapTo:-1, scanIdx:-1, missing:-1,
|
||
msg:`初始数组: [${a.join(', ')}]，n = ${n}。目标：把值 1~n 放到对应位置（值 v 应在索引 v-1）`
|
||
});
|
||
|
||
// Swap phase
|
||
for (let i = 0; i < n; i++) {
|
||
// Keep swapping until a[i] is in correct position or can't be placed
|
||
while (a[i] >= 1 && a[i] <= n && a[a[i] - 1] !== a[i]) {
|
||
const targetIdx = a[i] - 1;
|
||
const val = a[i];
|
||
const targetVal = a[targetIdx];
|
||
|
||
steps.push({
|
||
stage:'swap', arr:[...a], swapFrom:i, swapTo:targetIdx, scanIdx:-1, missing:-1,
|
||
msg:`交换 nums[${i}]=${val} → 目标位置 ${targetIdx}（值 ${val} 应在索引 ${val-1}）：swap(${i}, ${targetIdx})`
|
||
});
|
||
|
||
[a[i], a[targetIdx]] = [a[targetIdx], a[i]];
|
||
|
||
steps.push({
|
||
stage:'swapped', arr:[...a], swapFrom:i, swapTo:targetIdx, scanIdx:-1, missing:-1,
|
||
msg:`交换完成：nums[${i}]=${a[i]}, nums[${targetIdx}]=${a[targetIdx]}`
|
||
});
|
||
}
|
||
|
||
// If a[i] is already in correct position, or out of range, or duplicate
|
||
if (a[i] >= 1 && a[i] <= n && a[a[i] - 1] === a[i]) {
|
||
// already correct or duplicate at target, no step needed (already covered by while condition)
|
||
}
|
||
}
|
||
|
||
// Scan phase
|
||
for (let i = 0; i < n; i++) {
|
||
steps.push({
|
||
stage:'scan', arr:[...a], swapFrom:-1, swapTo:-1, scanIdx:i, missing:-1,
|
||
msg:`扫描索引 ${i}：期望值 ${i+1}，实际值 ${a[i]}${a[i] === i + 1 ? ' ✅ 匹配' : ' ❌ 不匹配'}`
|
||
});
|
||
|
||
if (a[i] !== i + 1) {
|
||
steps.push({
|
||
stage:'found', arr:[...a], swapFrom:-1, swapTo:-1, scanIdx:i, missing:i+1,
|
||
msg:`找到缺失！索引 ${i} 处期望 ${i+1}，实际为 ${a[i]}，缺失的第一个正数 = ${i+1}`
|
||
});
|
||
break;
|
||
}
|
||
|
||
// If we reach the end and all match
|
||
if (i === n - 1) {
|
||
steps.push({
|
||
stage:'found', arr:[...a], swapFrom:-1, swapTo:-1, scanIdx:n, missing:n+1,
|
||
msg:`所有位置都正确，缺失的第一个正数 = n+1 = ${n+1}`
|
||
});
|
||
}
|
||
}
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const n = s.arr.length;
|
||
|
||
let viz = '';
|
||
|
||
// Target position labels
|
||
viz += '<div style="font-size:13px;color:#475569;margin-bottom:4px;">📌 目标位置映射（值 v → 索引 v-1）</div>';
|
||
|
||
// Array with highlights
|
||
const hl = {};
|
||
if (s.stage === 'swap' || s.stage === 'swapped') {
|
||
if (s.swapFrom >= 0) hl[s.swapFrom] = 'orange';
|
||
if (s.swapTo >= 0) hl[s.swapTo] = 'orange';
|
||
if (s.stage === 'swapped') {
|
||
hl[s.swapFrom] = 'green';
|
||
hl[s.swapTo] = 'green';
|
||
}
|
||
}
|
||
if (s.stage === 'scan' || s.stage === 'found') {
|
||
// Highlight correctly placed and incorrectly placed
|
||
for (let i = 0; i < n; i++) {
|
||
if (s.arr[i] === i + 1) hl[i] = 'green';
|
||
else if (s.stage === 'scan' && i === s.scanIdx) hl[i] = 'active';
|
||
}
|
||
if (s.stage === 'found' && s.scanIdx < n) {
|
||
hl[s.scanIdx] = 'red';
|
||
}
|
||
}
|
||
|
||
const pointers = {};
|
||
if (s.stage === 'swap' || s.stage === 'swapped') {
|
||
if (s.swapFrom >= 0) pointers['i'] = s.swapFrom;
|
||
if (s.swapTo >= 0) pointers['tgt'] = s.swapTo;
|
||
}
|
||
if (s.stage === 'scan' && s.scanIdx >= 0 && s.scanIdx < n) {
|
||
pointers['i'] = s.scanIdx;
|
||
}
|
||
|
||
viz += renderArray(s.arr, {highlights: hl, pointers});
|
||
|
||
// Target slot labels
|
||
viz += '<div class="target-row" style="margin-top:-2px;">';
|
||
for (let i = 0; i < n; i++) {
|
||
let cls = '';
|
||
if (s.arr[i] === i + 1) cls = 'correct';
|
||
else if (s.arr[i] < 1 || s.arr[i] > n) cls = '';
|
||
else cls = 'wrong';
|
||
viz += `<span class="pos-tag ${cls}" style="min-width:40px;">${i+1}</span>`;
|
||
}
|
||
viz += '</div>';
|
||
viz += '<div style="font-size:11px;color:#94a3b8;margin-top:2px;">↑ 各位置期望值</div>';
|
||
|
||
// Swap visualization
|
||
if (s.stage === 'swap' && s.swapFrom >= 0 && s.swapTo >= 0) {
|
||
viz += `<div style="margin-top:10px;padding:8px 14px;background:#fff7ed;border-radius:8px;font-size:14px;">
|
||
交换：<code>nums[${s.swapFrom}]=${s.arr[s.swapFrom]}</code>
|
||
<span class="swap-arrow">⇄</span>
|
||
<code>nums[${s.swapTo}]=${s.arr[s.swapTo]}</code>
|
||
<div style="font-size:12px;color:#64748b;margin-top:4px;">值 ${s.arr[s.swapFrom]} 应在索引 ${s.arr[s.swapFrom] - 1}</div>
|
||
</div>`;
|
||
}
|
||
|
||
// Scan result
|
||
if (s.stage === 'found') {
|
||
viz += `<div style="margin-top:10px;padding:10px 14px;background:#ede9fe;border-radius:8px;font-size:15px;font-weight:700;color:#5b21b6;">
|
||
缺失的第一个正数 = ${s.missing}
|
||
</div>`;
|
||
}
|
||
|
||
// Formula
|
||
viz += '<div class="formula-box" style="margin-top:12px;">';
|
||
viz += `核心思想：<code>值 v (1≤v≤n) 放到索引 v-1</code><br>`;
|
||
viz += `<code>while nums[i] ∈ [1,n] && nums[nums[i]-1] ≠ nums[i]: swap(i, nums[i]-1)</code>`;
|
||
viz += '</div>';
|
||
|
||
$('vizArea').innerHTML = viz;
|
||
|
||
// Detail
|
||
let detail = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'swap') {
|
||
detail += `<div style="margin-top:6px;">条件检查：<code>${s.arr[s.swapFrom]} ∈ [1,${n}]</code> ✓ 且 <code>nums[${s.arr[s.swapFrom]-1}] ≠ ${s.arr[s.swapFrom]}</code> ✓ → 需要交换</div>`;
|
||
} else if (s.stage === 'swapped') {
|
||
detail += `<div style="margin-top:6px;">交换后检查 nums[${s.swapFrom}]=${s.arr[s.swapFrom]} 是否仍需继续交换</div>`;
|
||
}
|
||
$('detailContent').innerHTML = detail;
|
||
|
||
if (s.stage === 'found') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">
|
||
缺失的第一个正数 = <b>${s.missing}</b><br>
|
||
原地哈希后数组：[${s.arr.join(', ')}]
|
||
<div class="complexity">时间复杂度 O(n) ｜ 空间复杂度 O(1) ｜ 原地哈希</div>
|
||
</div>`;
|
||
}
|
||
|
||
$('hintText').textContent = s.msg;
|
||
|
||
const stages = [['init','初始'],['swap','交换'],['swapped','交换后'],['scan','扫描'],['found','找到']];
|
||
$('pipeline').innerHTML = stages.map(([k,l]) =>
|
||
`<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 = JSON.stringify(examples[0].input);
|
||
buildSteps(examples[0].input);
|
||
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 arr = JSON.parse($('inputArea').value);
|
||
if (!Array.isArray(arr) || arr.length === 0) throw new Error();
|
||
buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
} catch(e) { alert('请输入合法非空 JSON 数组，例如 [3,4,-1,1]'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.input);
|
||
buildSteps(e.input); 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 firstMissingPositive(nums):
|
||
n = len(nums)
|
||
for i in range(n):
|
||
# 把值 v 放到索引 v-1
|
||
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
|
||
idx = nums[i] - 1
|
||
nums[i], nums[idx] = nums[idx], nums[i]
|
||
# 扫描找缺失
|
||
for i in range(n):
|
||
if nums[i] != i + 1:
|
||
return i + 1
|
||
return n + 1`, {lang:'Python'});
|
||
})();
|
||
</script>
|
||
</body>
|
||
</html>
|