1570. Dot Product of Two Sparse Vectors

hash table O(n) time

class SparseVector {
public:

    SparseVector(vector<int> &nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i]) {
                m[i] = nums[i];
            }
        }
    }

    // Return the dotProduct of two sparse vectors
    int dotProduct(SparseVector& vec) {
        int res = 0;
        for (const auto &[i, v] : vec.m) {
            if (m.count(i)) {
                res += m[i] * vec.m[i];
            }
        }
        return res;
    }

    unordered_map<int, int> m;
};

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans = v1.dotProduct(v2);

常规拉链法
O(m+n) time

class SparseVector {
public:

    SparseVector(vector<int> &nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i]) {
                v.emplace_back(i, nums[i]);
            }
        }
    }

    // Return the dotProduct of two sparse vectors
    int dotProduct(SparseVector& vec) {
        int res = 0;
        for (int i = 0, j = 0, m = getDim(), n = vec.getDim(); i < m && j < n;) {
            int ii = getIdx(i), ij = vec.getIdx(j);
            if (ii == ij) {
                res += getNum(i++) * vec.getNum(j++);
            } else if (ii < ij) {
                ++i;
            } else {
                ++j;
            }
        }
        return res;
    }

    int getIdx(int i) {
        return v[i].first;
    }

    int getNum(int i) {
        return v[i].second;
    }

    int getDim() {
        return v.size();
    }

    vector<pair<int, int>> v;
};

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans = v1.dotProduct(v2);

二分拉链 worst case O(mlogm + nlogn) time
[1 3 5 7]
[2 4 6 8]

class SparseVector {
public:

    SparseVector(vector<int> &nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i]) {
                v.emplace_back(i, nums[i]);
            }
        }
    }

    int getIdx(int i) {
        return v[i].first;
    }

    int getNum(int i) {
        return v[i].second;
    }

    int getDim() {
        return v.size();
    }

    int lower_bound(int b, int e, int idx) {
        // return std::lower_bound(begin(v) + b, begin(v) + e, idx, [](const auto &p, int idx){ return p.first < idx; }) - begin(v); // 这个lambda相当于实现一个less，即找到第一个不小于的为止
        return std::lower_bound(begin(v) + b, begin(v) + e, make_pair(idx, INT_MIN)) - begin(v);
    }

    // Return the dotProduct of two sparse vectors
    int dotProduct(SparseVector& vec) {
        int res = 0;
        for (int i = 0, j = 0, m = getDim(), n = vec.getDim(); i < m && j < n;) {
            int ii = getIdx(i), ij = vec.getIdx(j);
            if (ii == ij) {
                res += getNum(i++) * vec.getNum(j++);
            } else if (ii < ij) {
                i = lower_bound(i + 1, m, ij);
            } else {
                j = vec.lower_bound(j + 1, n, ii);
            }
        }
        return res;
    }

    vector<pair<int, int>> v;
};

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans = v1.dotProduct(v2);