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

2021-03-30 HGNULB 约 5 分钟

文章信息 8 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决会员题 1-2 腾讯微软

题目描述

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

题意分析

两个向量的点积是“相同下标的两个值相乘，再把所有乘积相加”。稀疏向量中大部分元素为零，需要设计存储方式，让计算主要围绕真正可能产生贡献的位置进行。

只要某个位置有一侧为零，乘积就是零；因此只有两侧都非零的共同下标需要参与计算，相同数值出现在不同下标不能直接配对。

解法：哈希表存非零项

核心思路

[!blue]

构造向量时扫描原数组，把非零项存成“原始下标 → 值”的哈希映射。没有记录的下标都表示零，所以省掉它们不会改变点积；保留下标则能保证数组中的间隔和位置关系没有丢失。

点积查询选择非零项更少的一侧遍历。对其中每个下标，到另一张表查询对应值：存在则相乘累加，不存在则这一项贡献为零。任意非零贡献必然出现在较小表中，也会被唯一一次的下标遍历处理，因此没有遗漏或重复。

选择较小表只是减少查询次数，两侧在乘法中地位对称。代码交换的是局部表引用，并没有移动元素或修改原向量。全零向量对应空表，循环不会产生贡献，结果自然为 0。

解题步骤

构造时遍历输入数组，只把非零值按原始下标存入映射。

查询时比较两个映射的大小，令 a 指向较小者、b 指向较大者。

遍历 a 的每个下标，在 b 中查找相同下标；找到后将两侧的值相乘并累加。

返回乘积总和，整个查询不改变任一向量的存储内容。

代码实现

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)+1)$，其中 s₁、s₂ 是两侧非零项数。

空间复杂度：每个向量保存 $O(s+1)$ 的映射空间，查询额外工作区为 $O(1)$。

若只有一个向量稀疏、另一侧直接保存为普通数组，也可只遍历稀疏侧的非零下标，直接读取另一侧的数组元素，无需把稠密数组再转换为哈希表。

关键点总结

[!green]

零值可以省略，原始下标不能省略，它决定两个向量的哪一项相乘。

点积只在两侧非零下标的交集上产生贡献。

遍历较小映射，用哈希查找完成对应下标的配对，不需要依赖任何遍历顺序。

易错点总结

[!yellow]

只存非零值、丢掉原下标，会把原本不对应的位置错误相乘。

不能按两张哈希表各自的遍历顺序配对，哈希表没有向量的位置顺序。

Java 查找不存在的下标会得到 null，需要先判断再参与乘法，避免自动拆箱异常。

构造仍要读一遍完整输入数组，不能把初始化时间也写成只与非零项数有关。

相似题目

题目	难度	关联与区别
311. 稀疏矩阵的乘法	中等	稀疏矩阵每个输出格都是行列点积，可复用只遍历共同非零索引的乘加。
面试题 17.26. 稀疏相似度	困难	文档交集可看作0/1向量点积，本题进一步让每个非零索引带上不同权值。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/53120835

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！