LC3400 O(n^(4/3)lgn)

main.cpp

#ifdef ONLINE_JUDGE
#define NO_STD_INCLUDES
#endif

#include "tdzl/common.hpp"
#include "tdzl/utility/vector.hpp"
#include "tdzl/polynomial/convolution.hpp"

class Solution {
public:
    pair<unordered_map<int, int>, vector<int>> buildVisitLinkList(vector<int> nums) {
        vector<int> next(nums.size(), -1);
        unordered_map<int, int> first;

        for (int i = nums.size()-1; i >=0;i--) {
            int v = nums[i];
            auto itor = first.find(v);
            if (itor == first.end()) {
                first[v] = i+1;
            }
            else {
                next[i] = itor->second-1;
                itor->second = i+1;
            }
        }

        return make_pair(move(first), move(next));
    }

    int maximumMatchingIndices(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> result(n);

        int minCntToConv = (int)pow((double)n, 2 / 3);

        // 统计所有数量
        auto count1 = count<int, unordered_map<int, int>>(nums1);
        auto count2 = count<int, unordered_map<int, int>>(nums2);

        // 统计所有出现的数字
        auto allNums = nums1 + nums2;
        sort(allNums.begin(), allNums.end());
        allNums.erase(unique(allNums.begin(), allNums.end()), allNums.end());

        // 构造链表，这里一起构造了
        auto [first1, next1] = buildVisitLinkList(nums1);
        auto [first2, next2] = buildVisitLinkList(nums2);

        for (auto v : allNums) {
            if (count1[v] > minCntToConv && count2[v] > minCntToConv) {
                // calc by convolution
                vector<int> a(n), b(n);
                for (int i = first1[v] - 1; i != -1; i = next1[i]) {
                    a[i] = 1;
                }
                for (int j = first2[v] - 1; j != -1;j = next2[j]) {
                    b[j] = 1;
                }
                // calc \sum a[i]*b[i+k] => \sum a[i][n-1-i+k]
                reverse(b.begin(), b.end());
                vector<int> c = convolution(a, b); // with size 2n-1
                result[0] += c[n - 1];
                for (int i = 1;i < n; i++) {
                    result[i] += c[n-1-i] + c[2*n-1-i];
                }
            }
            else {
                // calc by value linked list
                for (int i = first1[v]-1; i != -1; i = next1[i]) {
                    for (int j = first2[v]-1; j != -1;j = next2[j]) {
                        result[(j + n - i) % n]++;
                    }
                }
            }
        }

        return max(result);
    }
};

#ifndef ONLINE_JUDGE
int main() {
    //vector<int> nums1 = { 3,1,2,3,1,2 };
    //vector<int>nums2 = { 1,2,3,1,2,3 };
    //vector<int> nums1 = { 1,4,2,5,3,1 };
    //vector<int>nums2 = { 2,3,1,2,4,6 };
    vector<int> nums1 = { 1,1,9,7 };
    vector<int> nums2 = { 1,1,9,7 };
    cout << Solution().maximumMatchingIndices(nums1, nums2) << endl;
    return 0;
}
#endif