首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何在随机列表中找到两个数字之间的最短距离,而不对列表进行排序。我的代码如下所示,我需要另一种快速方法

在给出另一种快速方法之前,让我们先理解一下问题的要求。你想要在一个随机列表中找到两个数字之间的最短距离,同时又不对列表进行排序。下面是一个快速的解决方案:

代码语言:txt
复制
def find_shortest_distance(nums, num1, num2):
    min_distance = float('inf')
    last_index = None

    for i, num in enumerate(nums):
        if num == num1 or num == num2:
            if last_index is not None and nums[last_index] != num:
                min_distance = min(min_distance, i - last_index)
            last_index = i

    return min_distance

这个解决方案的思路是遍历列表,同时记录上一次出现的目标数字的索引。当遇到目标数字时,我们检查上一次出现的目标数字是否与当前数字不同,如果是,则计算当前索引与上一次索引之间的距离,并更新最短距离。最后返回最短距离。

这种方法的时间复杂度是O(n),其中n是列表的长度。它不需要对列表进行排序,因此在处理大型列表时效率较高。

希望这个解决方案能满足你的需求。如果你有任何其他问题,请随时提问。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

Python 最常见 120 道面试题解析

何在 Python 中随机列表项目? 什么是 python 迭代器? 如何在 Python 中生成随机数? range&xrange 有什么区别? 你如何在 python 中写注释?...即使文件太大而无法放入内存,你代码也应该可以正常工作。 在 Python 中为数值数据集编写排序算法。 查看下面的代码,记下 A0,A1,...最终值。...检查给定数字n是否为2或0幂 计算将A转换为B所需位数 在重复元素数组中查找两个非重复元素 找到具有相同设置位数下一个较大和下一个较小数字 95.给定n个项目的重量和值,将这些物品放入容量为W背包中...子序列是以相同相对顺序出现序列,但不一定是连续。 找到给定序列最长子序列长度,以便对子序列所有元素进行排序,按顺序递增。...最短路径算法 在给定边缘加权有向图中找出每对顶点之间最短距离 图形实现 Kruskal最小生成树算法 拓扑排序

6.3K20

图解算法学习笔记

链表结构直观显示如下所示: 链表优势在插入元素方面,那数组优势又是什么呢? 2.2.2,数组 需要随机地读取元素时,数组效率很高,因为可迅速找到数组任何元素。...对数组进行快速排序,步骤如下: 1. 随机选择一个基准值; 2. 将数组分成两个子数组:小于基准值元素和大于基准值额元素; 3. 对这两个子数组进行排序。...在讨论快速排序运行时间前, 们再来看看最常见大O运行时间。常用排序算法运行时间,如下所示: 选择排序,其运行时间为O(n2),速度非常慢。...5.4,性能 散列表,数组,链表查找、插入、删除元素时间复杂度,如下所示: 在平均情况下,散列表查找(获取给定索引处值)速度与数组一样快,插入和删除速 度与链表一样快,因此它兼具两者优点...第六章,广度优先搜索 图算法:广度优先搜索(breadth-first search, BFS)算法 广度优先搜索让你能够找出两样东西之间最短距离,不过最短距离含义有很多!

1.6K20

学会这14种模式,你可以轻松回答任何编码面试问题

排序数组或链表中搜索对时,两个指针通常很有用;例如,当你必须将数组每个元素与其他元素进行比较时。 需要两个指针,因为仅使用指针,你将不得不不断地循环遍历数组以找到答案。...在许多情况下,两个指针可以帮助你找到具有更好空间或运行时复杂性解决方案。 确定何时使用"两指针"方法方法: 在处理排序数组(或链接列表)并且需要找到一组满足某些约束元素时,它将遇到一些问题。...数组中元素集是一对,三元组甚至是子数组 以下是具有两个指针模式一些问题: 平方排序数组(简单) 总计为零三元组(中) 比较包含退格键字符串(中) 3、快速指针或慢速指针 快速和慢速指针方法,也称为...然后,重复此过程以对所有元素进行排序遍历。 该模式如下所示: 将每个数组第一个元素插入最小堆中。 之后,从堆中取出最小(顶部)元素并将其添加到合并列表中。...如何识别K-way合并模式: 该问题将出现排序数组,列表或矩阵 如果问题要求你合并排序列表,请在排序列表中找到最小元素。

2.8K41

常用编程思想与算法

对于这个猜数字游戏使用二分法思想完成代码如下: #二分法 def two(lists,item): low=0 high=len(lists)-1 while low<=...那么你只能使用循环完成或者尾递归(这个高级方法还不会)。 快速排序   分而治之   假设要将一块土地均匀分成方块,并且确保方块最大。可以使用D&C策略。D&C算法是递归。   ...首先,从数组中选择一个元素,这个元素被称为基准值;   接下来,找出比基准值小元素以及比基准值大元素。   再对这两个子数组进行快速排序,直到满足基线条件。...合并排序总是O(n*log n)。但是这不是绝对,合并排序常量总是大于快速排序,所以一般情况下认为快速排序更快。   ...带负权边要使用贝尔曼福德算法计算(这个也不会)。   下面代码就实现了狄克斯特拉算法计算出最短路径代码

78910

《图解算法》系列学习(三)

狄克斯特拉算法 广度优先搜索是找出最短路径,狄克斯特拉算法是找出最快路径。广度优先搜索来查找两点之间最短路径,那时“最短路径”意思是段数最少。...如下所示: 狄克斯特拉算法包含下面4个步骤: (1) 找出最便宜节点,即可在最短时间内前往节点 (2) 对于该节点邻居,检查是否有前往它们更短路径,如果有,就更新其开销。...答案如下: hish和fish最长公共子串包含三个字母,hish 和vista最长公共子串包含两个字母。因此Alex很可能原本要输入是fish。...所以我们需要用最长公共子序列来就解决它,如下图: 伪代码如下: if word_a[i] == word_b[j] //两个字母相同 cell[i][j] = cell[i-1][j-1]...这种距离指出了两组数字之间相似程度。 2、回归 分类就是编组 回归就是预测结果 PS:前面计算两位用户距离时,使用都是距离公式。还有更合适公式吗?

47210

Python技巧101,每个新程序员都要知道

用Python编写代码已经有几年了,在过去6个月里,觉得自己已经成为了这方面的专家,以下是一些希望自己一开始就知道事情: 1、字符串操作 2、列表理解 3、lambda和map() 4、if、...哦,天哪,一旦了解了这些,整个世界都改变了(不是真的改变了,但已经很接近了)。这是对列表进行快速操作一种非常强大、直观和可读方法。...当你想做一些简单运算需要定义一个函数时,这就很有用了。以数字列表为例,我们如何在Python中对这样列表进行排序?...在浏览旧代码时,您会发现很多地方可以将简单条件if/else语句简化为一行代码。 # 5: zip() 还记得“map()”部分中关于在两个列表之间并行应用某些内容示例吗?...如果您觉得不对地方可以给我留言,我们一起讨论。 感谢你阅读。希望这对您有用!

60810

普林斯顿算法讲义(三)

我们试图实现以下 API: 令人惊讶是,KosarajuSharirSCC.java 仅通过在 CC.java 中添加几行代码就实现了该 API,如下所示: 给定一个有向图 G,使用 DepthFirstOrder.java...给定一个加权线图(无向连通图,所有顶点度为 2,除了两个端点度为 1),设计一个算法,在线性时间内预处理图,并能在常数时间内返回任意两个顶点之间最短路径距离。 部分解决方案。...编写一个程序,从标准输入中读取一个文本文件,并编制一个按字母顺序排列索引,显示哪些单词出现在哪些行,如下所示输入。忽略大小写和标点符号。...使用正则表达式提取在和标签之间所有文本。(?i)是另一种使匹配不区分大小写方法。$2指是第二个捕获子序列,即title标签之间内容。...此外,2 路合并操作需要 n 个单位时间。合并 k 个已排序数组最佳方法是什么? 解决方案. 将列表长度排序,使得 n1 < n2 < … < nk。重复地取最小两个列表并应用 2 路合并操作。

10710

真正统治世界十大算法,你知道吗?

不过在这篇文章中,让我们将算法定义限定在计算机算法上,所以剩下问题是:哪十个算法统治了世界?在此整理了一个小型列表,排名不分先后。 1. 归并排序快速排序和堆排序 ? 哪个排序算法最好?...快速排序是解决排序问题另一种途径,它使用就地分解算法,同时它也是一种分治算法。这个算法问题在于它是不稳定排序算法,但它在基于内存数组排序上确实非常高效。...这是一种图搜索算法,它被广泛应用在能够建模为图问题中,用以找出两个节点之间最短路径。...RSA算法用来解决一个简单而又复杂问题:怎样在不同平台和终端用户之间共享公钥,继而实现信息加密(想说明一下这个问题还没完全解决,想我们需要基于这个方向做更多工作)。 5....(推荐阅读:《当随机不够随机:一个在线扑克游戏教训》) 最后,想强调一下,上面这个列表经供参考,它并不完整。

1.4K80

统治世界十大算法

不过在这篇文章中,让我们将算法定义限定在计算机算法上,所以剩下问题是:哪十个算法统治了世界?在此整理了一个小型列表,排名不分先后。 1. 归并排序快速排序和堆排序 ? 哪个排序算法最好?...快速排序是解决排序问题另一种途径,它使用就地分解算法,同时它也是一种分治算法。这个算法问题在于它是不稳定排序算法,但它在基于内存数组排序上确实非常高效。...这是一种图搜索算法,它被广泛应用在能够建模为图问题中,用以找出两个节点之间最短路径。...RSA算法用来解决一个简单而又复杂问题:怎样在不同平台和终端用户之间共享公钥,继而实现信息加密(想说明一下这个问题还没完全解决,想我们需要基于这个方向做更多工作)。 5....(推荐阅读:《当随机不够随机:一个在线扑克游戏教训》) 最后,想强调一下,上面这个列表经供参考,它并不完整。

73790

从七桥问题开始:全面介绍图论及其应用

图表征:前言 这是一个很沉闷任务,要有耐心。记得数组和链表之间战争吗?用如果你需要快速访问元素就用数组,如果你需要快速插入/删除元素就用链表等。很难相信你会在像「怎样表示列表」这样问题上纠结。...国家代码可以被用两个字符,3 个字符或者 3 个数字来表示,我们会用 ushort 储存数字表达。...它可以在应用算法搜索两个节点间路径时定义。当然,我们还有更好方法来储存节点和边之间关系,关联矩阵。...基本上,我们需要通过搜索关键字进行快速查找,然后获得按关键字排序结果列表,这很可能应该是电影评级和/或基于用户个性化数据内部排名。...我们使用队列进行 BFS 迭代实现, DFS 则需要堆栈。图领域中一个最流行问题,同时也可能是你阅读本文原因之一是寻找图节点之间最短路径。这需要我们进行最后一个实验。

1.9K80

5大必知图算法,附Python代码实现

如下面的示意图所示,图中包含了各个城市和它们之间距离信息。 示意图 首先创建边列表列表中每个元素包含两个城市名称,以及它们之间距离。...2、最短路径 继续第一节中例子,我们拥有了德国城市群及其相互距离图表。为了计算从法兰克福前往慕尼黑最短路径,我们需要用到 Dijkstra 算法。...想象身处在沃尔玛商店,我们知道了各个过道之间距离,我们希望为从过道 A 到过道 D 客户提供最短路径。 如下所示,当我们知道了领英中用户一级连接、二级连接时,如何得知幕后信息呢?...—首先在图形上构建最小生成树,其中像素是节点,像素之间距离基于某种相似性度量(例如颜色,强度等),然后进行分割。...介数中心性衡量了特定节点出现在两个其他节点之间最短路径集次数。 度中心性:即节点连接数。

3.3K11

公司算法面试笔试题目集锦,个人整理,不断更新中

6.HMM与N-gram模型之间区别 7.梯度消失与梯度爆炸 8.奥卡姆剃须刀原理 9.TCP三次握手原理,为什么是三次不是其他次 10.进行数据处理时,如何过滤无用信息(例如利用正则表达式提取或者其他方法...2、请问如何在一个巨大数据集中找到中值? Uber 1、(对数据工程师)编写一个函数用来计算给定数字平方根(2 个小数点精度)。随后:避免冗余计算,现在使用缓存机制优化你功能。...例如:如果给函数二进制字符串 100 和 111,它应该返回 1011、你解决方案空间和时间复杂性如何? 2、编写一个函数,它接受两个排序列表,并在排序列表中返回它们并集。...领英 1、(对数据工程师)请编写一些代码来确定字符串中左右括号是否是平衡? 2、如何找到二叉搜索树中第二大元素? 3、请编写一个函数,它接受两个排序向量,并返回一个排序向量。...4、如果你有一个输入数字流,如何在运行过程中找到最频繁出现数字? 5、编写一个函数,将一个数字增加到另一个数字,就像 pow()函数一样。

2.1K30

复杂性思维第二版 三、小世界图

小世界属性”,即节点之间平均距离,以最短路径上边数来衡量,远远小于预期。...这个过程中,我们将看到两种新图算法:广度优先搜索(BFS)和 Dijkstra 算法,用于计算图中节点之间最短路径。 本章代码在本书仓库chap03.ipynb中。...Watts 和 Strogatz 定义了一个群聚系数,用于量化两个节点彼此连接,并同时连接到同一个节点可能性。 路径长度是两个节点之间平均距离度量,对应于社交网络中分离度。...Watts 和 Strogatz 发现,较小p值产生高群聚性图,正则图,短路径长度图,随机图。...它们不允许自环或多边;也就是说,节点不能拥有到它自身边,并且两个节点之间不能拥有多个边。 这是这个过程实现。

70510

PageRank、最小生成树:ML开发者应该了解五种图算法

下面以包含城市和城市间距离信息图为例,实现我们目的。 ? 带有随机距离图 首先创建一个带有城市名(边)和距离信息列表距离代表边权重。...该算法可以在不同数据上运行,从而满足上面提到各种用例。 最短路径 继续使用上述示例,现在我们有德国城市及城市之间距离图。如何找到从法兰克福(起始节点)到慕尼黑最短距离?...最终,令我惊讶是,这个算法成为著名成果之一。 应用 Dijkstra 算法变体在 Google 地图中有着广泛使用,用于寻找最短路线。 假设你有沃尔玛商店中各个过道位置和过道之间距离数据。...最具影响力用户子图如下所示: first_degree_connected_nodes = list(fb.neighbors(3437)) second_degree_connected_nodes...介数中心性:不仅拥有众多朋友用户很重要,将一个地理位置连接到另一个位置用户也很重要,因为这样可以让用户看到不同地点内容。 介数中心性量化了一个特定节点在其他两个节点之间最短路径中出现次数。

97640

【小白学游戏常用算法】二、A*启发式搜索算法

下面我们来了解一下A*算法相关理论知识: ?   如图,我们需要在迷宫中找到A点到B点一条最短可以通过路径,A和B直接被一面墙堵住了。...4个点每个进行处理(这里是限制了斜向移动),如果该点是可以通过并且该点不在close List列表中,则处理如下;   (4)如果该点正好是目标点,则把当前点作为该点父节点,并退出循环,设置已经找到路径标记...=G+H   在这里,F表示通往目标点代价,G表示从起始点移动到该点距离,H则表示从该点到目标点距离,比如图中,可以看到小狗附近格子代价值,其中左上角数字代表F值,左下角数字代表G值,右下角数字代表...当然,距离算法也可以采用其他方法,实际在游戏中,这个移动代价除了要考虑距离因素外,还要考虑当前格子游戏属性。...第二次循环时候把A右边点作为当前点,该点父节点就是A,这是处理当前点时候,只需要把当前点上下两个点放入open List中,因为左边A已经在close List中,右边是墙,所以直接被忽略

1.1K20

26 TIPS IN PYTHON

它通过抽取一系列不同地理编码服务APIs来工作。使你能够获得一个地方完整街道地址、纬度、经度和海拔。 还有一个有用distance类。以你喜欢单位计算两个位置之间距离。 ? ?...List comprehensions 关于Python编程,最喜欢事情之一是它列表生成。 这些表达式使得容易编写非常干净代码,读起来几乎像自然语言。...uuid 生成通用唯一标识(UUID)一种快速简单方法是使用Python标准库UUID模块。 ? ? 这可以产生一个随机128位数字,几乎可以肯定这个数字是唯一。...在给定集合中找到重复概率非常低。即使有万亿个UUID,重复存在概率也远低于十亿分之一。非常有用两行代码。 Virtual environments 这可能是最喜欢关于Python东西。...PyYaML允许你存储任何数据类型Python对象,以及任何用户定义类实例。 zip 对你来说,这是最后一招,真的很酷。曾经需要两个列表合成一个字典? ?

1.5K30

手把手:四色猜想、七桥问题…程序员眼里图论,了解下?(附大量代码和手绘)

图表示法:介绍 这是一项非常乏味任务,要有耐心。记得数组和链表之间竞争吗?如果你需要对元素进行快速访问,请使用数组;如果你需要对元素进行快速插入/删除等修改,请使用列表。...国家代码可以用2或3个字符或3个数字表示,我们会用数字表示并且用ushort表示每个国家代码。...这个例子重点在于对二叉搜索树进行有效范围查询。但和之前一样,在这里我们不会继研究冰山还没露出部分。 基本上,我们需要通过搜索关键字进行快速查找,然后获得按关键字排序结果列表。...那么现在问题是计算从车辆到乘客需要最小距离,也就是说,要找到最短路线。...前两步如下: 所有的节点都属于未访问集合,需要注意图示右侧表格。对于所有节点,它将包含从B到前一个(标记为“Prev”)节点所有最短距离。例如,从B到F距离是20,前一个节点是B。

2K40

70个NumPy练习:在Python下一举搞定机器学习矩阵运算

答案: 20.如何创建一个包含5到10之间随机浮点数二维数组? 难度:2 问题:创建一个5×3二维数组,以包含5到10之间随机浮点数。...答案: 42.如何在numpy中进行概率抽样? 难度:3 问题:随机抽样irisspecies,使setose是versicolor和virginica数量两倍。...答案: 44.如何按列排序二维数组? 难度:2 问题:根据sepallength列对iris数据集进行排序。 答案: 45.如何在numpy数组中找到最频繁出现值?...难度:2 问题:为给定数字数组a排序。 输入: 输出: 答案: 55.如何使用numpy对多维数组中元素进行排序? 难度:3 问题:创建一个与给定数字数组a相同形式排列数组。...难度:2 问题:从一维numpy数组中删除所有nan值 输入: 输出: 答案: 62.如何计算两个数组之间欧氏距离? 难度:3 问题:计算两个数组a和b之间欧式距离

20.6K42

30 个重要数据结构和算法完整介绍(建议收藏保存)

方法使用频率列表/映射来标记[0, n]范围内每个数字素数:如果 x 是素数,则ok[x]=0,否则ok[x]=1。...BFS 还用于计算源节点和所有其他节点之间最短距离。BFS 另一个版本是 Lee 算法,用于计算网格中两个单元格之间最短路径。 该算法首先访问源节点,然后访问将被推入队列邻居。...然后我们将每个顶点视为其他两个节点之间中间体。最短路径在每两对节点之间更新,任何节点 k 作为中间顶点。...它在稀有图上很有效,因为它时间复杂度是 O(|E|*log |V|)。 该算法方法如下:我们按权重递增顺序对所有边进行排序。然后,选取最小边。...这个属性实际上告诉我们一个顶点在它所有传出邻居都被弹出后从堆栈中弹出。因此,要对图进行拓扑排序,我们需要跟踪弹出顶点逆序列表。 哇,你已经到读了文章结尾。感谢您阅览!

1.7K31

使用 JavaScript 实现机器学习和神经学网络

欧氏距离提供结果是一个数字,该数字决定了相同长度两个数组之间相似性。...思考一下,假如我们想要确定一下数组2或者数组3哪个距离数组1更近。为了做到这一点,我们需要计算数组1和数组2之间欧氏距离。然后再计算数组1和数组3之间欧氏距离。两相比较,最短就是最相似的。...然后将这个通过向下采样得到网格与每个数字向下采样网格进行比较。如果要查看程序中经训练后得到网格,需要在字符列表中单击你希望看到字符。...紧接着,我们会计算出理想对齐角度。如下代码所示。 // 2....本质上,程序对列表两个城市进行了交换操作。所以我们必须保证这两个随机城市是不相同,因为一旦相同,这两个城市就不会发生交换。 交叉操作比较复杂。下面的代码实现了交叉函数。

1K100
领券