问题描述
小S正在帮助她的朋友们建立一个搜索引擎。为了让用户能够更快地找到他们感兴趣的帖子,小S决定使用倒排索引。倒排索引的工作原理是:每个单词都会关联一个帖子ID的列表,这些帖子包含该单词,且ID按从小到大的顺序排列。
例如,单词“夏天”可能出现在帖子1、帖子3和帖子7中,那么这个单词的倒排链就是[1, 3, 7]
。如果用户想同时找到包含“夏天”和“海滩”的帖子,小S需要找出两个倒排链的交集,且将结果按照从大到小的顺序输出。现在,给定两个单词的倒排链数组a
和b
,请你帮助小S找出同时包含这两个单词的帖子ID,并按从大到小的顺序返回结果。
测试样例
样例1:
输入:
a = [1, 2, 3, 7], b = [2, 5, 7]
输出:[7, 2]
样例2:
输入:
a = [1, 4, 8, 10], b = [2, 4, 8, 10]
输出:[10, 8, 4]
样例3:
输入:
a = [3, 5, 9], b = [1, 4, 6]
输出:[]
样例4:
输入:
a = [1, 2, 3], b = [1, 2, 3]
输出:[3, 2, 1]
解题思路:
问题理解
你需要找出两个有序数组 a
和 b
的交集,并将结果按从大到小的顺序返回。
数据结构选择
- 由于
a
和b
是有序数组,我们可以利用双指针法来高效地找到交集。 - 交集的结果需要按从大到小的顺序排列,因此我们可以使用一个
vector
来存储结果,并在最后反转这个vector
。
算法步骤
- 初始化双指针:分别指向数组
a
和b
的开始位置。 - 遍历数组:
- 如果
a[i]
等于b[j]
,则将这个值加入结果集,并移动两个指针。 - 如果
a[i]
小于b[j]
,则移动a
的指针。 - 如果
a[i]
大于b[j]
,则移动b
的指针。
- 如果
- 反转结果集:由于我们需要从大到小的顺序,最后反转结果集。
最终代码(C++):
今天终于把c++的判题系统放上去了,后面终于不需要转python了
#include <bits/stdc++.h>
#include <vector>
using namespace std;vector<int> solution(vector<int>& a, vector<int>& b) {vector<int> result;int i = 0, j = 0;// 双指针遍历while (i < a.size() && j < b.size()) {if (a[i] == b[j]) {result.push_back(a[i]);i++;j++;} else if (a[i] < b[j]) {i++;} else {j++;}}reverse(result.begin(), result.end());return result;
}int main() {vector<int> a1 = {1, 2, 3, 7};vector<int> b1 = {2, 5, 7};vector<int> res1 = solution(a1, b1);cout << (res1 == vector<int>{7, 2}) << endl;vector<int> a2 = {1, 4, 8, 10};vector<int> b2 = {2, 4, 8, 10};vector<int> res2 = solution(a2, b2);cout << (res2 == vector<int>{10, 8, 4}) << endl;vector<int> a3 = {3, 5, 9};vector<int> b3 = {1, 4, 6};vector<int> res3 = solution(a3, b3);cout << (res3 == vector<int>{}) << endl;vector<int> a4 = {1, 2, 3};vector<int> b4 = {1, 2, 3};vector<int> res4 = solution(a4, b4);cout << (res4 == vector<int>{3, 2, 1}) << endl;return 0;
}