- 正确答案：对于数组中每个元素，计算它与所有其他相同值元素的下标距离之和。例如数组 [1,3,1,1,2]，对下标0的元素1，其他相同元素在下标2和3，距离和为 |0-2| + |0-3| = 2 + 3 = 5；对下标2的元素1，距离和为 |2-0| + |2-3| = 2 + 1 = 3；下标3的元素1对应和为 |3-0| + |3-2| = 3 + 1 = 4。最终结果数组为 [5,0,3,4,0]（3和2均只出现一次，距离和为0）。 - 解答思路：暴力解法是O(n²)：对每个位置i，遍历整个数组找相同值元素并累加abs(i-j)。但存在明显优化空间——相同值元素的距离和可拆解为数学表达式。设某值v出现在下标集合{idx₀, idx₁, ..., idxₖ₋₁}（升序排列），对其中第p个位置idxₚ，其距离和为： sum_{q=0}^{p-1} (idxₚ - idx_q) + sum_{q=p+1}^{k-1} (idx_q - idxₚ) = p * idxₚ - sum_{q=0}^{p-1} idx_q + (sum_{q=p+1}^{k-1} idx_q) - (k-1-p) * idxₚ = (2p - k + 1) * idxₚ + (suffix_sum[p+1] - prefix_sum[p]) 因此，预处理每个值对应下标列表，并对每个列表计算前缀和，即可O(1)算出每个位置的贡献。总时间复杂度O(n)，空间O(n)。 - 深度知识讲解：本题本质考察「分组+前缀和优化」这一经典模式，核心在于将绝对值求和转化为带系数的线性组合。关键底层知识点包括：（1）绝对值函数的分段线性性质：|x - a_i| 在x固定时对a_i排序后可拆为左右两部分；（2）前缀和加速区间求和：prefix[i] = a₀+...+aᵢ₋₁，任意区间和a_l+...+a_r = prefix[r+1]-prefix[l]；（3）哈希分组：用HashMap>按值聚类下标，注意List中下标天然有序（因遍历原数组顺序插入），但为严谨应显式排序（实际无需，因插入顺序即升序）；（4）算法稳定性与边界处理：单元素组结果必为0；空组不出现；整数溢出风险（题目若给10⁵长度、10⁹下标，距离和可达10¹⁴，需用long存储中间结果）；（5）对比其他方法：树状数组/线段树也可维护动态前缀和，但本题离线静态，前缀和更优；若要求在线更新，则需考虑平衡BST或权值线段树维护有序下标集及和。 - 代码示例（Java风格伪代码，含详细注释）： ``` public long[] distance(int[] nums) { // Step1: 按值分组，记录每个值出现的所有下标 Map> groups = new HashMap<>(); for (int i = 0; i < nums.length; i++) { groups.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i); } long[] res = new long[nums.length]; // Step2: 对每组下标列表独立处理 for (List indices : groups.values()) { int k = indices.size(); if (k == 1) continue; // 单元素距离和为0，res已初始化为0 // 构建前缀和数组：prefix[j] = indices[0]+...+indices[j-1] long[] prefix = new long[k + 1]; for (int j = 0; j < k; j++) { prefix[j + 1] = prefix[j] + indices.get(j); } // 对组内每个位置p（对应原数组下标idx = indices.get(p)） for (int p = 0; p < k; p++) { int idx = indices.get(p); long leftSum = prefix[p]; // indices[0]到indices[p-1]之和 long rightSum = prefix[k] - prefix[p + 1]; // indices[p+1]到indices[k-1]之和 // 左侧有p个元素，每个贡献 (idx - indices[q]) => p*idx - leftSum // 右侧有(k-1-p)个元素，每个贡献 (indices[q] - idx) => rightSum - (k-1-p)*idx long distSum = (long) p * idx - leftSum + rightSum - (long)(k - 1 - p) * idx; res[idx] = distSum; } } return res; } ``` - 扩展知识：（1）进阶变体：若要求“每个元素与所有其他元素（不限值）的距离和”，则变成经典问题——排序后利用下标变换，答案为sum_{i} (2*i - n + 1) * sorted[i]（需证明）；（2）工程实践：大规模数据下可用并行流处理各group，但需注意HashMap并发安全，建议用ConcurrentHashMap或分段处理；（3）测试用例设计要点：必须覆盖空数组、单元素、全相同元素（如[5,5,5,5]）、逆序下标组（但实际不会发生，因插入顺序即升序）、大数溢出场景；（4）与LeetCode关联题：LC 1685. Sum of Absolute Differences in a Sorted Array 是本题的简化版（输入已排序且只有一种值），本题是其泛化；（5）底层内存视角：ArrayList底层Object[]连续存储，get(i)为O(1)；前缀和数组也是连续long[]，CPU缓存友好；HashMap的桶分布影响分组效率，但平均O(1)插入。

4.23 百度暑期实习 大数据存储研发 一面

全站热榜

创作者周榜

4.23 百度暑期实习大数据存储研发一面