- 正确答案：给定一个有序数组（非递减或非递增），求数组中绝对值不同的数的个数。例如，数组 [-5, -3, -1, 0, 1, 4, 4] 中，绝对值分别为 {5, 3, 1, 0, 1, 4}，去重后为 {0, 1, 3, 4, 5}，所以结果是 5。可以通过双指针法在 O(n) 时间内解决该问题，避免使用额外空间进行哈希集合存储。 - 解答思路：由于数组是有序的，但包含负数和正数，绝对值最小的元素可能出现在中间（如靠近0的位置）。我们无法直接遍历一次就判断所有绝对值是否重复，因为负数的绝对值在左边较大，正数的绝对值在右边逐渐变大。因此可以采用双指针策略： 1. 使用左指针 left 指向数组开头（最小值方向） 2. 使用右指针 right 指向数组末尾（最大值方向） 3. 比较两指针所指元素的绝对值： - 若某一方的绝对值更大，则先处理这一方，并移动对应指针 - 若相等，则两边都可以视为同一绝对值，同时跳过重复项 4. 维护一个变量 last_abs 记录上一个处理过的绝对值，避免重复计数 5. 遍历直到两个指针相遇这样可以从外向内“收缩”，按绝对值从小到大或从大到小顺序处理，从而实现去重统计。 - 深度知识讲解：考点一：有序数组的特性利用有序数组意味着我们可以不使用额外的数据结构（如 HashSet）来去重，而是通过指针扫描和比较完成去重。这是面试中常见的优化思想——利用输入数据的有序性降低时间/空间复杂度。考点二：双指针技巧（Two Pointers）双指针常用于有序数组中的查找、去重、配对等问题。本题的关键在于意识到负数部分的绝对值是递减的，而正数部分的绝对值是递增的。因此整个数组的绝对值分布呈现“V”型或“倒V”型，最大值在两端，最小值在中间附近。为了统一处理，我们可以从两端向中间扫描，每次取较大的绝对值先处理，或者取较小的先处理，取决于设计。这里我们选择：从两端向中间推进，每次选择当前更大的绝对值进行处理，并用 last_abs 记录已统计的最大绝对值，防止重复。考点三：去重逻辑设计去重要求不能重复记录同一个绝对值。我们需要在移动指针时跳过连续相同的原始值（比如多个 -3 或 4），但这还不够，因为 -3 和 3 是不同元素但相同绝对值。所以我们必须基于 abs(value) 进行去重。注意：即使原数组无重复元素，也可能有对称的正负数导致绝对值重复，如 -3 和 3。底层数据结构与算法原理：时间复杂度：O(n)，每个元素最多被访问一次空间复杂度：O(1)，仅使用常量额外空间算法类型：双指针 + 贪心去重对比其他方法：方法1：使用 HashSet 存储所有 abs(arr[i])，最后返回 set 大小。优点：简单直观缺点：空间复杂度 O(n) 不适合“手撕代码”要求高效的情况方法2：先全部转为绝对值再排序再去重但原数组已经是有序的，这样做反而破坏了原有结构，效率低方法3：双指针法（推荐）——充分利用有序性和对称性 - 代码示例（C++风格伪代码，可直接运行）： int countDistinctAbs(vector& arr) { int n = arr.size(); if (n == 0) return 0; int left = 0; int right = n - 1; int count = 0; int last_abs = INT_MIN; // 记录上一个被计入的绝对值 while (left <= right) { int left_abs = abs(arr[left]); int right_abs = abs(arr[right]); int current_abs; if (left_abs >= right_abs) { current_abs = left_abs; left++; // 跳过左侧相同绝对值的重复项（包括符号不同的情况） while (left <= right && abs(arr[left]) == current_abs) { left++; } } else { current_abs = right_abs; right--; // 跳过右侧相同绝对值的重复项 while (right >= left && abs(arr[right]) == current_abs) { right--; } } // 只有当 current_abs 不等于上次记录的绝对值时才计数 if (current_abs != last_abs) { count++; last_abs = current_abs; } } return count; } // 更简洁版本（推荐写法）： int countDistinctAbs(vector& arr) { int n = arr.size(); if (n == 0) return 0; int left = 0; int right = n - 1; int count = 0; int last_abs = -1; // 因为绝对值 >= 0，初始化为 -1 即可 while (left <= right) { int lval = abs(arr[left]); int rval = abs(arr[right]); int current_abs; if (lval > rval) { current_abs = lval; left++; // 跳过左侧剩余的相同绝对值 while (left <= right && abs(arr[left]) == current_abs) left++; } else { current_abs = rval; right--; while (right >= left && abs(arr[right]) == current_abs) right--; } if (current_abs != last_abs) { count++; last_abs = current_abs; } } return count; } - 扩展知识点：扩展1：若数组严格单调递增（无重复元素），是否可以简化？可以，但仍需处理对称值如 -3 和 3 的情况。此时只需在双指针过程中判断 abs 是否相等即可，无需内部 while 跳过重复。扩展2：能否从中间向两边扩展？可以！找到第一个非负数位置（lower_bound for 0），然后从中点分别向左（负数区）和向右（正数区）扩展，类似合并两个有序序列（绝对值递增），也可以实现 O(n) 时间、O(1) 空间。例如： int countDistinctAbsFromMiddle(vector& arr) { int n = arr.size(); if (n == 0) return 0; // 找到第一个 >= 0 的位置 int mid = 0; while (mid < n && arr[mid] < 0) mid++; int left = mid - 1; // 负数部分，从右往左：abs 递增 int right = mid; // 正数部分，从左往右：abs 递增 int count = 0; int last_abs = -1; while (left >= 0 || right < n) { int lval = (left >= 0) ? abs(arr[left]) : INT_MAX; int rval = (right < n) ? arr[right] : INT_MAX; int current_abs; if (lval <= rval) { current_abs = lval; left--; } else { current_abs = rval; right++; } if (current_abs != last_abs) { count++; last_abs = current_abs; } } return count; } 这种方法逻辑更清晰：将数组分为负数段（反转后绝对值递增）和非负段（本身绝对值递增），然后归并两个有序流，适合理解“绝对值有序”的本质。总结：本题考察点包括： 1. 对有序数组性质的理解 2. 双指针的设计能力 3. 去重逻辑的严谨性（含跨符号重复） 4. 边界处理（空数组、全负、全正、零的存在等）建议掌握两种解法：双端收缩法和中心展开归并法，前者适用于两端极值明显场景，后者更符合“绝对值有序”的思维模型。

美团-搜推算法实习面经-首页搜索

全站热榜

创作者周榜