- 正确答案：对于一个已排序的整数数组（可能含负数、零、正数），求其中绝对值互不相同的元素个数。最优解法是双指针法，时间复杂度O(n)，空间复杂度O(1)；返回值为不同|a[i]|的个数。例如：输入：[-5, -3, -1, 0, 2, 4, 6] → 绝对值集合为{0,1,2,3,4,5,6} → 输出7 输入：[-4, -2, -1, 1, 2, 3] → 绝对值集合为{1,2,3,4} → 输出4 输入：[-3, -3, -1, 0, 1, 1, 2] → 绝对值为{0,1,2,3} → 输出4 - 解答思路：由于原数组有序，负数在左、非负数在右（若有），而绝对值函数在负数区间单调递减，在非负数区间单调递增，整体呈“V型”分布（以0为谷底）。因此，最小绝对值往往出现在靠近0的位置（如0本身，或-1/1相邻处）。我们可以用双指针从两端向中间收缩，每次比较左右两端元素的绝对值： - 若 |left| < |right|，说明当前最小未处理的绝对值是|left|，记录它，left++，跳过所有等于|left|的后续绝对值（即跳过重复的abs(arr[left])）； - 若 |left| > |right|，则最小未处理的是|right|，记录它，right--，跳过重复； - 若 |left| == |right|，两者贡献同一个绝对值，只记一次，然后需同时收缩：left++ 且 right--，并跳过所有与该abs值相等的连续元素（注意避免越界）；持续直到 left <= right。用一个计数器统计不同绝对值个数即可。关键洞察：无需哈希表去重，也无需额外空间存绝对值——利用有序性+双指针可在线性时间内完成去重计数。 - 深度知识讲解：本题本质考察对**有序数组特性的深度运用**和**双指针模式的变体设计能力**，而非简单遍历+HashSet。底层知识点包括： 1. **绝对值函数的分段单调性**： f(x)=|x| 在 (-∞,0] 上严格递减（因x越小，|x|越大），在 [0,+∞) 上严格递增。因此，在有序数组中，绝对值序列呈现“先降后升”的形态（若含负数和正数），极小值点必在符号变化边界附近（即最后一个负数和第一个非负数之间）。这是双指针从两端向中间收敛的数学依据。 2. **双指针的贪心选择正确性证明**：每一步选取当前左右端中较小的绝对值，是因为该值是剩余子数组中全局最小的绝对值（由单调性保证）：设当前子数组为 arr[l..r]，因原数组有序，则 arr[l] ≤ arr[l+1] ≤ … ≤ arr[r]。若 arr[l] < 0 且 arr[r] ≥ 0，则 |arr[l]| 和 |arr[r]| 分别代表左侧递减段的最大值（即最小绝对值候选）、右侧递增段的最小值。但更严谨地说：整个子数组中最小绝对值一定出现在边界之一——因为内部任意索引k满足 l=0 的索引（可用二分或线性扫描）； ② 左指针i=p−1（指向最大负数），右指针j=p（指向最小非负数）； ③ 类似归并：比较|arr[i]| 和 arr[j]（因j侧非负，|arr[j]|==arr[j]），取较小者计入，移动对应指针，并跳过重复。然而，原题未限定必须用某种方式，且“双指针从两端”法在多数面试场景中被接受，因其简洁且平均表现好。其隐含假设是：数组足够长且负正均衡，最坏情况（全负或全正）也能正确处理。 3. **重复跳过逻辑与边界处理**：必须在每次选取一个绝对值后，将所有等于该绝对值的相邻元素一并跳过，否则会重复计数。例如 [-3,-3,-1,1,1,2]，当取| -1 | =1 后，需跳过所有绝对值为1的元素：即 -1、1、1 —— 但它们在数组中不连续！因此不能简单“跳过相邻相同abs”，而应：每次选定val = min(|arr[l]|, |arr[r]|)后，执行： while (l <= r && abs(arr[l]) == val) l++; while (l <= r && abs(arr[r]) == val) r--; 这样可清除所有等于val的绝对值（无论分布在左段还是右段）。该操作仍保持O(n)总时间，因为每个元素最多被访问两次（一次被选中，一次被跳过）。 - 伪代码（推荐实现）： ``` function countDistinctAbs(arr): if arr is empty: return 0 n = length(arr) left = 0, right = n - 1 count = 0 while left <= right: leftAbs = abs(arr[left]) rightAbs = abs(arr[right]) if leftAbs < rightAbs: count++ // 跳过所有等于 leftAbs 的绝对值（可能在左边连续，也可能右边有？但右边更大，不会等于） // 实际上只需跳过左边所有abs==leftAbs，因为右边都>leftAbs while left <= right and abs(arr[left]) == leftAbs: left++ else if leftAbs > rightAbs: count++ while left <= right and abs(arr[right]) == rightAbs: right-- else: // leftAbs == rightAbs count++ // 同时跳过左右所有等于该abs的元素 val = leftAbs while left <= right and abs(arr[left]) == val: left++ while left <= right and abs(arr[right]) == val: right-- return count ``` - 补充说明与易错点： 1. 全负数组（如[-5,-4,-3,-2,-1]）：leftAbs始终 < rightAbs？不，-5的abs=5，-1的abs=1，所以第一次是 leftAbs=5, rightAbs=1 → 进入 rightAbs 更小分支，计数1，right--；最终按绝对值升序处理：1,2,3,4,5 → 正确。 2. 全正数组（如[1,2,3,4,5]）：leftAbs恒小于rightAbs，每次只left++，计数5 → 正确。 3. 含零：[−2,−1,0,1,2] → 第一轮：|−2|=2, |2|=2 → 相等，count=1，然后跳过所有abs=2的：left从0→2（因abs[0]=2, abs[1]=1≠2, 所以只跳arr[0]？不对！while循环条件是abs(arr[left])==val，val=2，arr[0]=-2→满足，left=1；arr[1]=-1→abs=1≠2，停止；同理right从4→3（arr[4]=2→跳，arr[3]=1→停）。此时left=1, right=3，arr[1]=-1, arr[3]=1 → abs都是1 → 再次相等，count=2，跳过所有abs=1：left→2（arr[1]和arr[3]都被跳），right→2，最后left==right==2，arr[2]=0，abs=0，进入相等情况，count=3 → 正确（{0,1,2}）。 - 进阶扩展：若要求返回具体的绝对值列表（有序），可在计数的同时用链表或动态数组收集val；若数组极大且内存受限，该算法仍适用，因仅用O(1)额外空间；对比HashSet方案：时间O(n)，空间O(n)，且无法利用有序性，属于通用解法，但非最优；若数组无序，则必须用HashSet或排序预处理（O(n log n)），凸显本题“有序”条件的价值。 - 可运行的Python代码（带测试）： ``` def count_distinct_abs(arr): if not arr: return 0 left, right = 0, len(arr) - 1 count = 0 while left <= right: l_abs = abs(arr[left]) r_abs = abs(arr[right]) if l_abs < r_abs: count += 1 # Skip all elements with same absolute value from left while left <= right and abs(arr[left]) == l_abs: left += 1 elif l_abs > r_abs: count += 1 # Skip all elements with same absolute value from right while left <= right and abs(arr[right]) == r_abs: right -= 1 else: # l_abs == r_abs count += 1 val = l_abs while left <= right and abs(arr[left]) == val: left += 1 while left <= right and abs(arr[right]) == val: right -= 1 return count # Test cases print(count_distinct_abs([-5,-3,-1,0,2,4,6])) # 7 print(count_distinct_abs([-4,-2,-1,1,2,3])) # 4 print(count_distinct_abs([-3,-3,-1,0,1,1,2])) # 4 print(count_distinct_abs([1,2,3,4,5])) # 5 print(count_distinct_abs([-5,-4,-3,-2,-1])) # 5 print(count_distinct_abs([0])) # 1 print(count_distinct_abs([])) # 0 ```

美团搜推算法日常实习二面

全站热榜

创作者周榜