js算法题
最新回答
看轻也就看清
2026-10-27 08:37:34
核心思想缓升：通过相邻元素的比较和交换，将较大的元素逐步“冒泡”到数组末尾。
- 时间复杂度：
最好情况（已排序）：O(n)（通过优化标志位实现）。
最坏/平均情况：O(n2)。
- 空间复杂度：O(1)（原地排序）。
- 稳定性：稳定（相等元素不交换）。
代码优化：
function bubbleSort(arr) { let len = arr.length; let swapped; for (let i = 0; i < len - 1; i++) { swapped = false; for (let j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; swapped = true; } } if (!swapped) break; // 无交换时提前终止 } return arr;}2. 快速排序核心思想：分治法，选取基准值（pivot）将数组分为两部分，递归排序。
- 时间复杂度：
平均：O(n log n)。
最坏（已排序数组）：O(n2)。
- 空间复杂度：O(log n)（递归栈）。
- 稳定性：不稳定（分区操扰谈老作可能改变相等元素顺序）。
代码优化（三数取中法选基准）：
function quickSort(arr, left = 0, right = arr.length - 1) { if (left >= right) return; const pivotIndex = partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex + 1, right); return arr;}function partition(arr, left, right) { const mid = Math.floor((left + right) / 2); const pivot = arr[mid]; [arr[mid], arr[right]] = [arr[right], arr[mid]]; // 将基准移至末尾 let i = left; for (let j = left; j < right; j++) { if (arr[j] < pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; } } [arr[i], arr[right]] = [arr[right], arr[i]]; // 基准归位 return i;}3. 数组默认排序注意：sort() 默认按 Unicode 码点排序，需提供比较函数。
arr.sort((a, b) => a - b); // 升序arr.sort((a, b) => b - a); // 降序4. 乘积最大的三个数关键点：考虑负数乘积可能更大（如两个负数×正数）。
function maxProduct(arr) { arr.sort((a, b) => a - b); const n = arr.length; return Math.max( arr[0] * arr[1] * arr[n - 1], // 最小侍拿两个×最大 arr[n - 1] * arr[n - 2] * arr[n - 3] // 最大三个 );}5. 连续数组缺失数数学方法：高斯求和公式。
function findMissing(arr, lower, upper) { const expectedSum = (upper * (upper + 1)) / 2 - (lower * (lower - 1)) / 2; const actualSum = arr.reduce((sum, num) => sum + num, 0); return expectedSum - actualSum;}6. 数组去重方法对比：
- ES6：[...new Set(arr)]（简洁）。
- ES5：arr.filter((v, i) => arr.indexOf(v) === i)（兼容性好）。
动态追踪最小值和最大差值：
function maxDifference(arr) { if (arr.length < 2) return 0; let min = arr[0], maxDiff = 0; for (let i = 1; i < arr.length; i++) { if (arr[i] > min) maxDiff = Math.max(maxDiff, arr[i] - min); else min = arr[i]; } return maxDiff;}8. 数组交集哈希表法：
function intersection(arr1, arr2) { const set = new Set(arr1); return [...new Set(arr2.filter(v => set.has(v)))];}9. 回文字符串优化：避免反转字符串，用双指针：
function isPalindrome(s) { s = s.toLowerCase().replace(/[^a-z0-9]/g, ''); let left = 0, right = s.length - 1; while (left < right) { if (s[left] !== s[right]) return false; left++; right--; } return true;}10. 双栈实现队列核心：输入栈处理入队，输出栈处理出队。
class Queue { constructor() { this.input = []; this.output = []; } enqueue(x) { this.input.push(x); } dequeue() { if (!this.output.length) { while (this.input.length) { this.output.push(this.input.pop()); } } return this.output.pop() || undefined; }}11. 字母计数扩展：支持大小写不敏感：
function countLetters(s) { const map = {}; s.toLowerCase().replace(/[^a-z]/g, '').split('').forEach(c => { map[c] = (map[c] || 0) + 1; }); return map;}12. 原型继承ES6 Class 语法：
class O { static count = 0; constructor(name) { this.name = name; O.count++; }}const a = new O('a'); // O.count → 1总结- 排序算法：根据场景选择（冒泡适合小数据，快速排序平均高效）。
- 数组操作：去重用 Set，交集用哈希表。
- 字符串处理：回文检查注意边界条件。
- 原型链：理解 prototype 和 __proto__ 的关系。
热门标签
