Knowledge_Repository

主题

Teeker2026-04-06
1624
6.1m

华为机考高频题解析：快速排序、两数之和、二分查找 ​

好的，我来帮你把这三道高频机考题逐一拆解，讲清楚思路、代码逻辑和关键细节，让你彻底搞懂它们。

1. 快速排序（quickSort） ​

题目描述 ​

给定一个数组，使用快速排序算法将其升序排列。

核心思路 ​

快速排序的核心是“分治思想”：

  1. 选基准（pivot）：从数组中选一个元素作为基准（这里选中间元素）。

  2. 分区（partition）：把数组分成三部分——比基准小的元素、等于基准的元素、比基准大的元素。

  3. 递归排序：对“比基准小”和“比基准大”的两个子数组分别递归排序。

  4. 合并结果：把排序后的左子数组、基准元素、排序后的右子数组合并成最终数组。

代码逐行解析 ​

JavaScript

function quickSort(arr) {
  // 递归终止条件：数组长度 <= 1 时，本身就是有序的，直接返回
  if (arr.length <= 1) return arr;

  // 1. 选基准：取数组中间的元素
  const pivot = arr[Math.floor(arr.length / 2)];

  // 2. 分区：把数组分成三部分
  const left = arr.filter(x => x < pivot);   // 比基准小的元素
  const middle = arr.filter(x => x === pivot); // 等于基准的元素
  const right = arr.filter(x => x > pivot);  // 比基准大的元素

  // 3. 递归排序 + 合并
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

关键细节 ​

  • **为什么选中间元素当基准？**这是为了避免极端情况（如数组已有序时）导致的时间复杂度退化，让分区更均衡。

  • filter ** 的作用**：这是一种简洁的分区写法，但会额外创建数组，空间复杂度略高。在性能要求极高的场景下，可以用原地分区（双指针交换元素）来优化空间。

  • 时间复杂度：平均 O(n log n)，最坏 O(n²)（如数组已有序且选首/尾为基准时），但实际中是效率很高的排序算法。

2. 两数之和（twoSum） ​

题目描述 ​

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

核心思路 ​

这道题的最优解法是用**哈希表（Map）**来降低时间复杂度：

  1. 遍历数组：对于每个元素 nums[i]，计算它与目标值的差值 diff = target - nums[i]。

  2. 检查哈希表：如果差值 diff 已经在哈希表中，说明之前遍历过的某个元素和当前元素的和正好是 target，直接返回这两个元素的下标。

  3. 存入哈希表：如果差值不在哈希表中，就把当前元素的值和下标存入哈希表，继续遍历。

代码逐行解析 ​

JavaScript

function twoSum(nums, target) {
  const map = new Map(); // 哈希表：键是数组元素值，值是元素下标

  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i]; // 计算当前元素需要的“补数”

    // 如果补数已经在哈希表中，说明找到了答案
    if (map.has(diff)) {
      return [map.get(diff), i]; // 返回补数的下标和当前下标
    }

    // 否则，把当前元素和下标存入哈希表
    map.set(nums[i], i);
  }

  return []; // 遍历完没找到，返回空数组
}

关键细节 ​

  • **为什么用哈希表？**哈希表的查找和插入操作都是 O(1)，所以整个算法的时间复杂度是 O(n)，比暴力法（O(n²)）高效很多。

  • **为什么不能先把所有元素存入哈希表再遍历？**这样会导致无法处理“同一个元素被使用两次”的情况（如 nums = [3,3], target = 6）。边遍历边存入，就能保证每个元素只和它之前的元素配对。

  • **哈希表存的是什么？**存的是“元素值 → 下标”的映射，这样可以通过值快速找到对应的下标。

3. 二分查找（binarySearch） ​

题目描述 ​

给定一个升序排列的整数数组 arr 和一个目标值 target，写一个函数搜索 arr 中的 target，如果目标值存在返回它的下标，否则返回 -1。

核心思路 ​

二分查找的前提是数组有序，它通过不断缩小搜索范围来找到目标值：

  1. 初始化边界：左边界 low = 0，右边界 high = arr.length - 1。

  2. 循环缩小范围：在 low <= high 的条件下，计算中间位置 mid。

  3. 比较中间值：

    • 如果 arr[mid] === target：找到目标，返回下标 mid。

    • 如果 arr[mid] < target：目标在右半部分，更新左边界 low = mid + 1。

    • 如果 arr[mid] > target：目标在左半部分，更新右边界 high = mid - 1。

  4. 未找到：如果循环结束还没找到，返回 -1。

代码逐行解析 ​

JavaScript

function binarySearch(arr, target) {
  let low = 0, high = arr.length - 1; // 初始化左右边界

  while (low <= high) { // 只要范围有效，就继续查找
    const mid = Math.floor((low + high) / 2); // 计算中间位置（向下取整）

    if (arr[mid] === target) {
      return mid; // 找到目标，返回下标
    } else if (arr[mid] < target) {
      low = mid + 1; // 目标在右边，更新左边界
    } else {
      high = mid - 1; // 目标在左边，更新右边界
    }
  }

  return -1; // 遍历完没找到，返回-1
}

关键细节 ​

  • **为什么用 ** Math.floor((low + high) / 2) **？**这是为了避免 low + high 数值过大导致溢出。在 JS 中数字精度较高，溢出风险小，但这是通用的安全写法。另一种等价写法是 low + Math.floor((high - low) / 2)。

  • **循环条件为什么是 ** low <= high **？**因为当 low === high 时，范围里还有最后一个元素需要检查。如果写成 low < high，会漏掉这个元素。

  • 时间复杂度：O(log n)，每次循环都把搜索范围缩小一半，效率非常高。

总结 ​

题目核心考点时间复杂度空间复杂度
快速排序分治思想、递归平均 O(n log n)，最坏 O(n²)平均 O(log n)，最坏 O(n)
两数之和哈希表的使用、空间换时间O(n)O(n)
二分查找有序数组的高效查找、边界处理O(log n)O(1)
这三道题都是华为机考的高频考点，理解它们的思路比背代码更重要。

如果需要，我可以帮你把这三道题的测试用例和边界情况整理成一份清单，让你写完代码后可以快速验证是否正确。需要吗？

（注：文档部分内容可能由 AI 生成）

最近更新