LeetCode 1570. 两个稀疏向量的点积

2021-03-30 HGNULB 约 5 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 1570. 两个稀疏向量的点积

题意分析

这是一道设计题：需要实现一个 SparseVector 类，构造函数接收一个整数数组，并提供 dotProduct 方法计算当前向量与另一个同长度向量的点积。点积的定义就是对应下标相乘后求和。

题干反复强调「稀疏」二字，这不是修饰而是考点。稀疏意味着数组里绝大多数元素是 0，而 0 乘任何数都是 0，对结果毫无贡献。所以真正需要参与计算的只有非零项，把全部 n 个位置都扫一遍是在做大量无效乘法。

题目也明确提示了「如果向量非常大且只有很少的非零元素，能否优化你的算法」，这是在要求把复杂度从「与向量长度相关」变成「与非零元素个数相关」。

数组长度上限是 $10^5$，元素值域是 $[-100, 100]$。乘积单项最大 $10^4$，累加 $10^5$ 项后上界约 $10^9$，勉强在 int 范围内但已经很接近，因此累加时用 64 位更稳妥。

作为设计题还要考虑分工：构造函数只调用一次而 dotProduct 可能被调用很多次，所以预处理的成本可以摊到构造阶段，查询阶段要尽量轻。

边界上，两个向量可能完全没有共同的非零下标，此时点积为 0；也可能其中一个是全零向量，结果同样是 0。

解法：哈希表存非零项

核心思路

点积中只要任一侧的元素为 0，该下标贡献就是 0。构造向量时只保存“下标到非零值”的映射，查询便无需遍历零元素。

计算时遍历非零项较少的向量，用下标查询另一侧；只有查询命中才累加乘积。点积满足交换律，因此交换遍历侧不会改变结果。

不变量：处理完遍历侧的一部分非零项后，answer 等于这些下标在两向量中的乘积之和。未存储的下标至少有一侧为零，贡献必为零。

正确性：所有可能产生非零贡献的下标都包含在两张映射的交集中。算法遍历较小映射并逐一查询另一张表，恰好累加交集内每个下标一次；交集外项贡献均为零，因此结果就是完整点积。

解题步骤

构造函数扫描原数组，只把非零元素写入哈希表。

dotProduct 比较两张表大小，选择较小者遍历。

对每个 (index,value) 查询另一张表；命中才累加乘积。

返回累加结果。

[1,0,0,2,3] 与 [0,3,0,4,0] 只有下标 3 同时非零，点积为 2*4=8。

边界上，全零向量的映射为空，循环不执行并返回 0；两侧有非零项但下标完全不重合时也返回 0。

代码实现

import java.util.HashMap;
import java.util.Map;

class SparseVector {
    private final Map<Integer, Integer> values;

    SparseVector(int[] nums) {
        values = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                values.put(i, nums[i]);
            }
        }
    }

    public int dotProduct(SparseVector vec) {
        Map<Integer, Integer> a = values;
        Map<Integer, Integer> b = vec.values;
        if (a.size() > b.size()) {
            Map<Integer, Integer> t = a;
            a = b;
            b = t;
        }

        long answer = 0;
        for (Map.Entry<Integer, Integer> entry : a.entrySet()) {
            Integer other = b.get(entry.getKey());
            if (other != null) {
                answer += (long) entry.getValue() * other;
            }
        }
        return (int) answer;
    }
}

type SparseVector struct {
	values map[int]int
}

func Constructor(nums []int) SparseVector {
	values := make(map[int]int)
	for i, v := range nums {
		if v != 0 {
			values[i] = v
		}
	}
	return SparseVector{values: values}
}

func (v *SparseVector) DotProduct(vec SparseVector) int {
	a := v.values
	b := vec.values
	if len(a) > len(b) {
		a, b = b, a
	}
	answer := 0
	for idx, v := range a {
		if v2, ok := b[idx]; ok {
			answer += v * v2
		}
	}
	return answer
}

复杂度分析

时间复杂度：构造为 $O(n)$；查询期望为 $O(\min(s_1,s_2))$，其中 s1、s2 是两侧非零项数。

空间复杂度：每个向量为 $O(s)$，查询额外空间为 $O(1)$。

关键点总结

稀疏数据只存非零项，让查询成本取决于有效项数量。

点积只需处理两侧非零下标的交集。

遍历较小表、查询较大表，将期望查询次数降到较小非零项数。

哈希遍历顺序不影响加法结果；设计无需维护排序。

Java 使用 64 位中间和，再按题目返回类型转为 int。

易错点总结

把零也存入表：空间和查询都会退化到 $O(n)$，失去稀疏优化意义。

用元素值而非下标作键：[5,0,5] 的两个 5 会互相覆盖。

未判断查询是否命中就拆箱：Java 的 null 会触发空指针异常。

两张表各遍历一次并都累加：共同非零项会被计算两遍。

查不到时默认值设为 1：本应贡献 0 的下标会产生伪乘积。

相似题目

题目	难度	考察点
311. 稀疏矩阵的乘法	中等	稀疏思想升到二维，需要按非零项的行列关系组织遍历顺序
349. 两个数组的交集	简单	同样是「遍历小的、查大的」，但比较的是元素值且要去重
350. 两个数组的交集 II	简单	需要保留重复次数，哈希表存的是计数而非位置
170. 两数之和 III - 数据结构设计	简单	同为设计题，考的是把成本放在 `add` 还是 `find` 的权衡
986. 区间列表的交集	中等	两个有序序列的双指针归并，正是本题「有序存储」变体的标准答案
88. 合并两个有序数组	简单	双指针同步推进的最简形态，用来打牢归并式遍历的下标控制
303. 区域和检索 - 数组不可变	简单	同属「构造阶段预处理换查询阶段常数时间」的设计范式