按线性时间排序？ - 腾讯云开发者社区

文章/答案/技术大牛

发布

1回答

按线性时间在按列排序的数组中搜索值

arrays、algorithm、sorting、time-complexity、big-o

如何在线性时间O(n)按列排序的数组中搜索值？int[][] m = { {4, 6, 5}, }; 如何在线性时间O(n)内解决这个问题？

浏览 3提问于2022-05-31得票数 2

1回答

考虑重复的有向多依赖图的线性排序

algorithm、haskell、graph、topological-sort

在线性序中，如果A要求B，则B必须在A之前，反之，如果A使B无效，则B必须在A之后。考虑到在排序中顶点可能不止发生一次.如何从这样的图构造线性序？B `invalidates` AC `invalidates` A朴素实现朴素的实现通过从没有传入边缘的所有

浏览 5提问于2017-06-02得票数 3

1回答

我想知道这段代码的总体时间复杂度！下面的代码对数组进行排序

arrays、python-3.x、time-complexity

我使用堆函数对数组进行排序。sortedArray.append(heapq.heappop(heapArray))arr = sortedArray这段代码对数组进行排序

浏览 9提问于2022-06-08得票数 -1

2回答

按线性时间排序数组

algorithm、runtime、radix-sort

我被困在这个问题上:给定n个整数数组在0，1，…，n^5-1的范围内，你如何在线性运行时对它们进行排序？(O(n))，更广泛地说，如果范围是，你会怎么做？描述适当的算法并进行解释。我的第一个想法是在这两种情况下将数字转换为基n，然后使用基排序(使用计数排序作为排序算法)，但是我被告知我不能指望从十进制基到基n的转换是O(1)，所以基本上我被困住了，因为我不知道我能不能这样做……会很乐意帮忙的

浏览 15提问于2022-04-01得票数 0

1回答

如何在线性时间内对长度为k的n个单词进行排序？

algorithm、sorting、computer-science

我想实现一个算法来排序长度为k的n个单词，这些单词将只包含英语单词(因此从a-z)。我尝试使用计数排序，通过将单词->字符的第一个元素转换为整数表示，然后使用计数排序(线性时间排序)，这种类型的工作，但它只排序第一个字符，即当两个或更多的单词有相同的第一个字符时，他们没有按他们的第二个字符排序有没有人可以指导我，或者给我一个提示，让我在线性时间内对这n个单词进行排序？

浏览 1提问于2018-03-19得票数 0

1回答

拆分后维护二维点的排序数组(C++)

c++、sorting、split

在第一步中，我创建了一个按x坐标排序的数组和一个按y坐标排序的数组。然后，我将x排序的数组一分为二。如何从这两部分重构相应的y排序数组的两部分，而不是再次按y坐标排序。这似乎在线性时间内是可能的，并且应该是相当容易的。谢谢。

浏览 0提问于2013-01-28得票数 0

回答已采纳

1回答

单项值和有限项值的背包问题

algorithm、knapsack-problem、greedy

我认为最困难的部分是O(n)，因为我们不应该对任何东西进行排序。有谁知道吗？

浏览 10提问于2019-04-16得票数 1

回答已采纳

1回答

所有类别的线性时间排序

algorithm、sorting

我有一个也许很愚蠢的想法因为我们有用于约束类别的线性时间排序算法，比如使用计数排序、基数排序的整数。我们可以使用这些线性时间排序算法对所有这些数字进行线性时间排序吗？

浏览 0提问于2012-10-14得票数 1

回答已采纳

1回答

是否有任何算法，即O(n)时间，并必然使用O(n)辅助空间？

algorithm

我注意到，可以在线性时间内解决的问题，可以调整为使用不超过O(1)辅助空间。取路径图的加权独立集问题。如果只需要总重量，就需要O(1)空间。其它允许线性时间算法的问题有:最大子阵和问题、按i位置旋转一维向量、将BST转换为排序的双链表等。

浏览 2提问于2013-10-14得票数 1

回答已采纳

3回答

按特定顺序排列数组中的元素

arrays、algorithm、sorting

重新排列数组，例如A<=A1>=A2<=A3>=A4<=A5等等编辑:数组没有排序，必须在线性时间O(N)中进行排序。我无法在线性时间内找到解决方案，我得到的最接近的方法是对数组进行排序，然后重新排列元素。有人知道如何在线性时间内完成吗？这能在线性时间内完成吗？我建议的解决方案是在nlogn时间内对数组进行排序，然后用i-1和i+1

浏览 4提问于2016-02-04得票数 3

回答已采纳

1回答

有人能给我解释一下基数吗？

sorting、radix-sort、array-algorithms

我试图在javascript中实现基排序。但是，我不知道怎么做基数排序！

浏览 5提问于2015-03-29得票数 1

回答已采纳

2回答

我正在为面试的代码类型问题做准备，我遇到了最近的k个问题，但是给出了一个排序数组。此问题需要从数组的输入值中按值找到k个最近的元素。这个问题的答案是相当直截了当的，我没有任何问题决定一个线性时间算法来解决它。然而，在这个问题上的工作让我思考。在线性时间内，给定一个未排序的数组，能解决这个问题吗？我的第一个想法是使用堆，这会给出一个O(nlogk)时间复杂度的解决方案，但我试图确定它是否有可能想出一个O(n)的解决方案？我在考虑可能使用类似quicks

浏览 17提问于2022-10-02得票数 2

1回答

从邻接列表表示中删除重复顶点和自循环的图算法

algorithm、graph

给定有向多图的邻接列表表示，有向多图是否有O(V+E)算法将其转化为无向简单图？该算法显然应该使用最小的空间。

浏览 5提问于2012-10-10得票数 0

5回答

最快排序技术

algorithm、sorting、optimization

在过去的几天里，我一直在尝试各种排序算法。从1) O(n^2)时间复杂度的排序算法开始2) O(n log n)时间复杂度的就地和非就地排序技术我想知道是否有排序算法可以在线性时间或更短的时间内排序。我听说过基数排序，在最好的情况下，它接近线性时间排序，具有一定的空间复杂性。有没有人能开导我？

浏览 2提问于2012-05-16得票数 3

回答已采纳

1回答

按线性时间对特定序列进行排序

algorithm、sorting、data-structures

我要面对的挑战是：如何用O(n)时间复杂度来解决这个问题？

浏览 4提问于2020-08-26得票数 0

回答已采纳

2回答

对Map中的时间戳进行排序

scala

我有一些元组的列表，如果这个元组包含时间戳，就是一个元组。我尝试按时间戳对此列表进行排序，并将其转换为map，如下所示： println(s"--list before order ${vendingMachineResults.map(v => v._5.timestamp我希望时间戳按升序排列，但事实并非如此。

浏览 0提问于2013-02-01得票数 0

回答已采纳

1回答

找到强连接的部件？

algorithm、graph、computer-science

我的书定义了一种在线性时间内找到有向图强连通分量的方法。此外，其他几种寻找强连通分量的算法(即Tarjan算法)也能在线性时间内找到强连通分量。然而，所有这些算法都要求对图的顶点进行降后值排序(顶点离开的时间)。常用的排序算法，如Mergesort取O(n log )时间。因此，如果通过 post 值对顶点列表排序需要O(n log )时间，那么这些算法如何能够在线性时间内完成强连

浏览 0提问于2012-06-19得票数 0

1回答

线性时间最小轴平行包围盒

algorithm、bounding-box、convex-hull、radix-sort

问题为了做到这一点，我想使用最小轴-平行包围盒，可以用线性时间计算，旋转卡尺从凸多边形开始。不幸的是，我没有凸多边形和计算它将需要O(nlogn)的时间，因为凸包。你有更好的想法来计算最

浏览 0提问于2018-01-02得票数 1

回答已采纳

2回答

Java8为SortedSet优化的最大过滤器？

java、filter、java-8、sortedset

如果我根据某个最大值或最小值筛选一个排序集或映射，Java 8会不加考虑地检查每个元素的条件，还是使用“排序”进行优化？如果没有，是否有更好的方法仍然使用Java 8并行？.); 按要求澄清:让我们假设“数字”很大。如果我们检查每个元素，如果它是<= 100 (或任何其他数字)，我们会浪费大量的时间。一个有效的实现将二进制搜索在排序的集合上，并在日志时间而不是线性时间中识别截止值，然后使用一些内部集特性来在这个截止时间创建一个子

浏览 1提问于2014-02-16得票数 1

回答已采纳

3回答