我将实现一个时间复杂度为O(n)的LRU（Least Recently Used）缓存算法。虽然哈希表+双向链表是O(1)的经典实现，但这里我将使用数组来实现一个直观的O(n)版本。

<!DOCTYPE html>
<html lang="en">
<head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><title>LRU缓存算法实现</title><style>* {box-sizing: border-box;margin: 0;padding: 0;font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;}body {background: linear-gradient(135deg, #1a2a6c, #b21f1f, #fdbb2d);min-height: 100vh;display: flex;justify-content: center;align-items: center;padding: 20px;}.container {background-color: rgba(255, 255, 255, 0.95);border-radius: 16px;box-shadow: 0 10px 30px rgba(0, 0, 0, 0.3);width: 100%;max-width: 700px;padding: 30px;margin: 20px;}header {text-align: center;margin-bottom: 30px;}h1 {color: #2c3e50;font-size: 2.8rem;margin-bottom: 10px;background: linear-gradient(to right, #3498db, #e74c3c);-webkit-background-clip: text;-webkit-text-fill-color: transparent;}.subtitle {color: #7f8c8d;font-size: 1.2rem;margin-top: 10px;}.algorithm-info {background-color: #f8f9fa;border-radius: 12px;padding: 20px;margin-bottom: 30px;border-left: 4px solid #3498db;}.algorithm-info h2 {color: #2c3e50;margin-bottom: 15px;}.algorithm-info ul {padding-left: 25px;}.algorithm-info li {margin-bottom: 10px;line-height: 1.6;}.complexity {background-color: #e3f2fd;padding: 15px;border-radius: 8px;margin-top: 15px;}.code-container {background-color: #2d3748;border-radius: 12px;padding: 25px;color: #e2e8f0;overflow-x: auto;margin-bottom: 30px;}pre {font-family: 'Fira Code', 'Consolas', monospace;font-size: 1rem;line-height: 1.6;margin: 0;white-space: pre-wrap;}.test-section {background-color: #f8f9fa;border-radius: 12px;padding: 25px;}.test-section h2 {color: #2c3e50;margin-bottom: 20px;padding-bottom: 10px;border-bottom: 2px solid #e0e0e0;}.test-controls {display: grid;grid-template-columns: 1fr 1fr;gap: 15px;margin-bottom: 20px;}.test-control {display: flex;flex-direction: column;}label {font-weight: 600;margin-bottom: 8px;color: #34495e;}input, button {padding: 12px;border: 2px solid #e0e0e0;border-radius: 8px;font-size: 1rem;}input:focus {border-color: #3498db;outline: none;box-shadow: 0 0 0 3px rgba(52, 152, 219, 0.2);}button {background: linear-gradient(to right, #3498db, #2c3e50);color: white;border: none;cursor: pointer;transition: all 0.3s;font-weight: bold;grid-column: span 2;}button:hover {transform: translateY(-2px);box-shadow: 0 5px 15px rgba(0, 0, 0, 0.2);}.test-results {margin-top: 25px;background-color: white;border-radius: 8px;padding: 20px;border: 2px solid #e0e0e0;font-family: 'Consolas', monospace;min-height: 150px;}.result-item {margin-bottom: 10px;padding-bottom: 10px;border-bottom: 1px solid #eee;}.cache-state {margin-top: 20px;padding-top: 20px;border-top: 2px dashed #3498db;}.cache-items {display: flex;flex-wrap: wrap;gap: 10px;margin-top: 15px;}.cache-item {background: linear-gradient(to right, #3498db, #2c3e50);color: white;padding: 10px 15px;border-radius: 6px;font-weight: bold;display: flex;flex-direction: column;align-items: center;min-width: 80px;}.cache-key {font-size: 0.9rem;opacity: 0.8;}.cache-value {font-size: 1.2rem;margin-top: 5px;}footer {text-align: center;margin-top: 30px;color: #7f8c8d;font-size: 0.9rem;}</style>
</head>
<body><div class="container"><header><h1>LRU缓存算法实现</h1><p class="subtitle">时间复杂度O(n)的数组实现方案</p></header><div class="algorithm-info"><h2>LRU缓存算法原理</h2><ul><li><strong>LRU (Least Recently Used)</strong>：最近最少使用缓存淘汰策略</li><li><strong>核心思想</strong>：当缓存空间不足时，优先淘汰最久未被访问的数据</li><li><strong>数据结构</strong>：使用数组存储缓存项，最近访问的项在数组尾部</li><li><strong>操作规则</strong>：<ul><li><code>get(key)</code>：获取缓存值，并将该项移到数组末尾</li><li><code>put(key, value)</code>：添加缓存项，如果已存在则更新并移到末尾</li><li>当缓存满时，删除数组开头的元素（最久未使用）</li></ul></li></ul><div class="complexity"><p><strong>时间复杂度分析</strong>：</p><ul><li><code>get</code>操作：O(n) - 需要遍历数组查找key</li><li><code>put</code>操作：O(n) - 查找key + 可能删除第一个元素</li><li><strong>注意</strong>：虽然时间复杂度为O(n)，但对于小型缓存效率足够</li></ul></div></div><div class="code-container"><pre><code>class LRUCache {constructor(capacity) {this.capacity = capacity; // 缓存容量this.cache = []; // 缓存存储数组}// 获取缓存值get(key) {for (let i = 0; i < this.cache.length; i++) {const item = this.cache[i];if (item.key === key) {// 将访问的项移到数组末尾（表示最近使用）this.cache.splice(i, 1);this.cache.push(item);return item.value;}}return -1;}// 添加缓存put(key, value) {// 检查是否已存在for (let i = 0; i < this.cache.length; i++) {const item = this.cache[i];if (item.key === key) {// 更新值并移到数组末尾item.value = value;this.cache.splice(i, 1);this.cache.push(item);return;}}// 如果缓存已满，删除最久未使用的项（数组开头）if (this.cache.length >= this.capacity) {this.cache.shift();}// 添加新项到数组末尾this.cache.push({ key, value });}// 获取当前缓存状态（用于展示）getCacheState() {return [...this.cache];}
}</code></pre></div><div class="test-section"><h2>测试LRU缓存</h2><div class="test-controls"><div class="test-control"><label for="keyInput">键(Key):</label><input type="text" id="keyInput" placeholder="例如: user1"></div><div class="test-control"><label for="valueInput">值(Value):</label><input type="text" id="valueInput" placeholder="例如: Alice"></div><button id="putBtn">添加缓存 (put)</button><div class="test-control"><label for="getKeyInput">获取键(Key):</label><input type="text" id="getKeyInput" placeholder="输入要获取的key"></div><button id="getBtn">获取缓存 (get)</button></div><div class="test-results"><h3>操作结果:</h3><div id="results"></div><div class="cache-state"><h3>当前缓存状态 (最近使用 → 最久未使用):</h3><div class="cache-items" id="cacheState"></div></div></div></div><footer><p>LRU缓存算法实现 | 时间复杂度O(n) | 数组实现方案</p></footer></div><script>// LRU缓存类实现class LRUCache {constructor(capacity = 3) {this.capacity = capacity; // 缓存容量this.cache = []; // 缓存存储数组}// 获取缓存值get(key) {for (let i = 0; i < this.cache.length; i++) {const item = this.cache[i];if (item.key === key) {// 将访问的项移到数组末尾（表示最近使用）this.cache.splice(i, 1);this.cache.push(item);return item.value;}}return -1;}// 添加缓存put(key, value) {// 检查是否已存在for (let i = 0; i < this.cache.length; i++) {const item = this.cache[i];if (item.key === key) {// 更新值并移到数组末尾item.value = value;this.cache.splice(i, 1);this.cache.push(item);return;}}// 如果缓存已满，删除最久未使用的项（数组开头）if (this.cache.length >= this.capacity) {this.cache.shift();}// 添加新项到数组末尾this.cache.push({ key, value });}// 获取当前缓存状态（用于展示）getCacheState() {return [...this.cache];}}// 初始化缓存const lruCache = new LRUCache(3);// 更新缓存状态显示function updateCacheDisplay() {const cacheState = document.getElementById('cacheState');cacheState.innerHTML = '';const cacheItems = lruCache.getCacheState();// 从右向左显示，让最近使用的在右边for (let i = cacheItems.length - 1; i >= 0; i--) {const item = cacheItems[i];const itemEl = document.createElement('div');itemEl.className = 'cache-item';itemEl.innerHTML = `<div class="cache-key">${item.key}</div><div class="cache-value">${item.value}</div>`;cacheState.appendChild(itemEl);}}// 添加测试结果function addResult(message) {const results = document.getElementById('results');const resultItem = document.createElement('div');resultItem.className = 'result-item';resultItem.textContent = message;results.appendChild(resultItem);results.scrollTop = results.scrollHeight;}// 绑定事件document.getElementById('putBtn').addEventListener('click', function() {const keyInput = document.getElementById('keyInput');const valueInput = document.getElementById('valueInput');const key = keyInput.value.trim();const value = valueInput.value.trim();if (key && value) {lruCache.put(key, value);addResult(`添加缓存: ${key} = ${value}`);updateCacheDisplay();// 清空输入keyInput.value = '';valueInput.value = '';keyInput.focus();} else {alert('请输入键和值');}});document.getElementById('getBtn').addEventListener('click', function() {const getKeyInput = document.getElementById('getKeyInput');const key = getKeyInput.value.trim();if (key) {const value = lruCache.get(key);if (value !== -1) {addResult(`获取缓存: ${key} = ${value} (缓存命中)`);} else {addResult(`获取缓存: ${key} (缓存未命中)`);}updateCacheDisplay();// 清空输入getKeyInput.value = '';getKeyInput.focus();} else {alert('请输入要获取的键');}});// 初始显示updateCacheDisplay();addResult('LRU缓存已初始化，容量为3');</script>
</body>
</html>

LRU缓存算法实现说明

核心类：LRUCache

class LRUCache {constructor(capacity) {this.capacity = capacity; // 缓存容量this.cache = []; // 缓存存储数组}// 获取缓存值get(key) {for (let i = 0; i < this.cache.length; i++) {const item = this.cache[i];if (item.key === key) {// 将访问的项移到数组末尾（表示最近使用）this.cache.splice(i, 1);this.cache.push(item);return item.value;}}return -1;}// 添加缓存put(key, value) {// 检查是否已存在for (let i = 0; i < this.cache.length; i++) {const item = this.cache[i];if (item.key === key) {// 更新值并移到数组末尾item.value = value;this.cache.splice(i, 1);this.cache.push(item);return;}}// 如果缓存已满，删除最久未使用的项（数组开头）if (this.cache.length >= this.capacity) {this.cache.shift();}// 添加新项到数组末尾this.cache.push({ key, value });}
}

时间复杂度分析

  • get操作：O(n) - 需要遍历数组查找key
  • put操作：O(n) - 查找key + 可能删除第一个元素
  • 空间复杂度：O(n) - 存储所有缓存项

算法特点

  1. 最近使用项保持在数组末尾：每次访问或更新都会将项移到数组末尾
  2. 最久未使用项在数组开头：当缓存满时，删除数组开头的元素
  3. 简单直观：易于理解和实现
  4. 适合小型缓存：对于容量不大的缓存，效率足够

使用示例

// 创建容量为3的缓存
const cache = new LRUCache(3);// 添加缓存
cache.put("name", "Alice");
cache.put("age", 30);
cache.put("city", "New York");// 获取缓存
cache.get("name"); // 返回 "Alice"，同时将该项移到缓存末尾// 添加新项（缓存已满，淘汰最久未使用的"age"）
cache.put("country", "USA");

这个实现提供了一个时间复杂度为O(n)的LRU缓存解决方案，通过数组操作实现了LRU的核心逻辑。