首页
学习
活动
专区
工具
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.9K41

    常用编程思想与算法

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

    81910

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

    狄克斯特拉算法 广度优先搜索是找出最短的路径,而狄克斯特拉算法是找出最快的路径。广度优先搜索来查找两点之间的最短路径,那时“最短路径”的意思是段数最少。...如下图所示: 狄克斯特拉算法包含下面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:前面计算两位用户的距离时,使用的都是距离公式。还有更合适的公式吗?

    56810

    普林斯顿算法讲义(三)

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

    17210

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

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

    1.5K80

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

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

    63810

    统治世界的十大算法

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

    75690

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

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

    2K80

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

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

    3.4K11

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

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

    2.2K30

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

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

    74510

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

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

    1K40

    【小白学游戏常用算法】二、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.2K20

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

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

    2.2K40

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

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

    1K100

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

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

    2.9K31

    26 TIPS IN PYTHON

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

    1.5K30

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

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

    20.7K42
    领券