字节青训-小S的倒排索引

问题描述

小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

算法步骤

  1. 初始化双指针:分别指向数组 a 和 b 的开始位置。
  2. 遍历数组
    • 如果 a[i] 等于 b[j],则将这个值加入结果集,并移动两个指针。
    • 如果 a[i] 小于 b[j],则移动 a 的指针。
    • 如果 a[i] 大于 b[j],则移动 b 的指针。
  3. 反转结果集:由于我们需要从大到小的顺序,最后反转结果集。

最终代码(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;
}

 运行结果:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/465926.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

讲讲分布式与集群的区别?

大家好&#xff0c;我是锋哥。今天分享关于【讲讲分布式与集群的区别&#xff1f;】面试题。希望对大家有帮助&#xff1b; 讲讲分布式与集群的区别&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 在现代计算和信息技术领域&#xff0c;分布式系统和集…

大数据新视界 -- 大数据大厂之 Impala 性能优化:解锁大数据分析的速度密码(上)(1/30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

大数据新视界 -- 大数据大厂之 Impala 性能优化:数据存储分区的艺术与实践(下)(2/30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

【实用教程】Blazor 文件管理器中引入分页功能

分页是一项重要功能&#xff0c;可帮助我们有效地加载大量数据。我们的 Syncfusion Blazor 文件管理器允许在分段页面中显示文件和文件夹&#xff0c;从而更轻松地浏览大型目录。在文件管理器组件中处理大量数据时&#xff0c;此功能非常方便。此功能可用于有效地加载大量数据。…

C++上机实验|多态性编程练习

1.实验目的 (1)理解多态性的概念。 (2)掌握如何用虚函数实现动态联编 (3)掌握如何利用虚基类。 2.实验内容 设计一个飞机类 plane,由它派生出歼击机类fighter和轰炸机类 bomber,歼击机类fighter 和轰炸机类bomber 又共同派生出歼轰机(多用途战斗机)。利用虚函数和虚基类描述…

CSS弹性布局:灵活布局的终极指南

在网页设计中&#xff0c;CSS 弹性布局&#xff08;Flexbox&#xff09;是一个不可或缺的工具。它能帮助你轻松地排列和对齐元素&#xff0c;尤其是在响应式设计中表现出色。今天&#xff0c;我们就来深入探讨一下 Flexbox 的各个属性&#xff0c;让你彻底掌握这个强大的布局工…

Java:二维数组

目录 1. 二维数组的基础格式 1.1 二维数组变量的创建 —— 3种形式 1.2 二维数组的初始化 \1 动态初始化 \2 静态初始化 2. 二维数组的大小 和 内存分配 3. 二维数组的不规则初始化 4. 遍历二维数组 4.1 for循环 ​编辑 4.2 for-each循环 5. 二维数组 与 方法 5.1…

SQL,力扣题目1767,寻找没有被执行的任务对【递归】

一、力扣链接 LeetCode_1767 二、题目描述 表&#xff1a;Tasks ------------------------- | Column Name | Type | ------------------------- | task_id | int | | subtasks_count | int | ------------------------- task_id 具有唯一值的列。 ta…

Spring Security-02-Spring Security认证方式-HTTP基本认证、Form表单认证、HTTP摘要认证、前后端分离安全处理方案

Lison <dreamlison163.com>, v1.0.0, 2024.06.01 Spring Security-02-Spring Security认证方式-HTTP基本认证、Form表单认证、HTTP摘要认证、前后端分离安全处理方案 文章目录 Spring Security-02-Spring Security认证方式-HTTP基本认证、Form表单认证、HTTP摘要认证、…

3.1、软件需求分析

软件需求分析 1、 需求分析定义及获取2、 需求分析过程2.1 需求提炼2.2 需求描述2.3 需求验证 3、 需求分析任务3.1 软件需求规格文档编制沟通活动通用任务集软件需求规格说明的原则软件需求规格说明的结构 1、 需求分析定义及获取 需求分析&#xff1a;确定系统必须具有的功能…

qt QStandardItemModel详解

1、概述 QStandardItemModel是Qt框架中提供的一个基于项的模型类&#xff0c;用于存储和管理数据&#xff0c;这些数据可以以表格的形式展示在视图控件&#xff08;如QTableView、QTreeView等&#xff09;中。QStandardItemModel支持丰富的数据操作&#xff0c;包括添加、删除…

Ubuntu18.04更换PREEMPT RT内核

文章目录 1 安装环境2 下载实时内核3 安装必要库和软件4 配置4.1 解压kernel压缩包4.2 进入kernel文件夹4.2.1 操作步骤4.2.2 修改配置文件 5 构建和安装6 启动显示内核选择界面7 启动界面选择实时内核版本进入8 uname -a查看操作系统内核信息 1 安装环境 Ubuntu 18.04原生内核…

立冬到了,选择Codigger暖心陪伴

立冬了&#xff0c;寒风渐起&#xff0c;但Codigger开发者们依然热情如火&#xff0c;编程的热情不会因为冬天而减退&#xff0c;相反&#xff0c;更加激情澎湃。就像立冬的清晨&#xff0c;虽然寒冷&#xff0c;却有着一种清新的气息&#xff0c;让我们一起迎接新的挑战&#…

全文检索ElasticSearch到底是什么?

学习ElasticSearch之前&#xff0c;我们先来了解一下搜索 1 搜索是什么 ① 概念&#xff1a;用户输入想要的关键词&#xff0c;返回含有该关键词的所有信息。 ② 场景&#xff1a; ​ 1互联网搜索&#xff1a;谷歌、百度、各种新闻首页&#xff1b; ​ 2 站内搜索&#xff…

Ansys Zemax | 手机镜头设计 - 第 4 部分:用LS-DYNA进行冲击性能分析

该系列文章将讨论智能手机镜头模组设计的挑战&#xff0c;从概念和设计到制造和结构变形分析。本文是四部分系列中的第四部分&#xff0c;它涵盖了相机镜头的显式动态模拟&#xff0c;以及对光学性能的影响。使用Ansys Mechanical和LS-DYNA对相机在地板上的一系列冲击和弹跳过程…

Follow软件的使用入门教程

开篇 看到很多兄弟还不知道怎么用这个当下爆火的浏览器&#xff01;在这里简单给需要入门的小伙伴一些建议&#xff1a; 介绍 简单解释一下&#xff0c;RSS 意思是简易信息聚合&#xff0c;用户可以通过 RSS 阅读器或聚合工具自主订阅并浏览各个平台的内容源&#xff0c;不用…

Redis数据库测试和缓存穿透、雪崩、击穿

Redis数据库测试实验 实验要求 1.新建一张user表&#xff0c;在表内插入10000条数据。 2.①通过jdbc查询这10000条数据&#xff0c;记录查询时间。 ②通过redis查询这10000条数据&#xff0c;记录查询时间。 3.①再次查询这一万条数据&#xff0c;要求根据年龄进行排序&#…

无root权限在Linux虚拟环境安装指定版本python

创建虚拟环境见 Linux创建虚拟环境&#xff0c;并在虚拟环境中运行项目_如何进入虚拟zhi环境再打开项目-CSDN博客 若使用python -m venv创建虚拟环境则无法指定python版本&#xff0c;需要单独安装 1.在官网Download Python | Python.org 下载对应版本的python包 例如我这里…

OCR、语音识别与信息抽取:免费开源的AI平台在医疗领域的创新应用

一、系统概述 在医疗行业中&#xff0c;大量数据来自手写病历、医学影像报告、患者对话记录等非结构化数据源。这些数据常常存在信息碎片化和管理困难的问题&#xff0c;给医务人员的工作带来了不便。思通数科AI多模态能力平台正是为了解决这一行业痛点而生&#xff0c;产品集…

Rust移动开发:Rust在iOS端集成使用介绍

iOS调用Rust 上篇介绍了 Rust移动开发&#xff1a;Rust在Android端集成使用介绍, 这篇主要看下iOS上如何使用Rust&#xff0c;Rust可以给移动端开发提供跨平台&#xff0c;通用组件支持。 该篇适合对iOS、Rust了解&#xff0c;想知道如何整合调用和编译的&#xff0c;如果想要…