是否可以在少于O(n)的时间内从排序列表中删除重复项？
是的，可以在少于O(n)的时间内从排序列表中删除重复项。
一种常见的方法是使用双指针法。我们可以使用两个指针，一个指针用于遍历列表，另一个指针用于指向当前不重复的元素位置。开始时，两个指针都指向列表的第一个元素。
然后，我们开始遍历列表，如果当前元素与前一个元素相同，则说明它是重复的，我们将忽略它并继续遍历。如果当前元素与前一个元素不同，则说明它是不重复的，我们将把它移到指针指向的位置，并将指针向后移动一位。
这样，当遍历完整个列表后，指针指向的位置就是去重后的列表的最后一个元素的位置。我们可以根据指针的位置将列表截断，从而删除重复项。
这种方法的时间复杂度是O(n)，其中n是列表的长度。因为我们只需要遍历一次列表，并且每次操作都是常数时间的。
腾讯云相关产品推荐：腾讯云云数据库MySQL。腾讯云云数据库MySQL是一种高性能、可扩展、高可用的关系型数据库服务，适用于各种规模的应用程序。它提供了自动备份、容灾、监控等功能，可以帮助用户轻松管理和维护数据库。了解更多信息，请访问腾讯云云数据库MySQL产品介绍页面：https://cloud.tencent.com/product/cdb
相关·内容
在面试中，我被要求从列表中删除重复的学生对象，其中学生对象可能包含不同的属性，条件是我不应该使用set或hashmap。
浏览 1提问于2012-05-28得票数 1
回答已采纳
1回答
查找所有可能的产品将花费O(n^2)，并验证产品是否已经在列表中，这将花费我的O(n^2)。因此，总数为O(n^4)。
我希望优化这个解决方案。我首先想到的是删除列表B中的副本。在我的例子中，我有3作为一个副本。我不需要再用重复</
浏览 1提问于2019-10-23得票数 2
假设您有一台特殊的高性能计算机。在这台计算机中，有一个专门的k优化寄存器库，其中k> 2。每个寄存器都可以用来存储一个键值对，因此这组寄存器可以存储到k个键值对。此登记册库可在O(1)时间内支持下列操作：
返回一个键值对(x，y)，它是最小的键x，从寄存器库中返回.此返回对也将从此寄存器库中删除。设计了一种利用这组寄存器
浏览 0提问于2018-10-10得票数 0
回答已采纳
我正在尝试解决一个问题，在O(n)时间内，给定容器前面和后面的两个前向迭代器，我希望删除容器中出现次数至少< this number >的所有元素。例如，给定一个字符串向量("john"，"hello"，"one"，"yes"，"hello"，"one")，并且我想删除出现次数少于2次的所有元素，那么我<
浏览 0提问于2013-02-20得票数 1
3回答
维护排序顺序C#的集合。
、、、、
每个Bar都有一个属性，可以对其排序(类型为TimeSpan，表示持续时间)，Bar是一个不可变的对象-也就是说，持续时间不会随着算法的运行而改变。目前，对于每个Foo，我还维护了如果要排序的话列表中第一位的Bar (即最短持续时间的Bar )。这里有一个n Foos的列表，每个列表都有最多m个Bars。直到现在为止，这个类一直为我服务。我现在希望为用户提供几种选
浏览 0提问于2015-07-23得票数 13
回答已采纳
1回答
给出了从1到n的混合整数列表(没有重复的)，例如4,2,6,1,5,3和排序列表1,2,3,4,5,6。
现在中位数是3.5。当查看排序列表1,2,3,4,5,6时，这可以用O(1)时间计算。现在从混合列表中删除4。有没有在O(1)时间内更新中值的算法？我想
浏览 5提问于2016-01-24得票数 0
我将字符串作为arraylist中的元素，我想使用Java在O(logn)时间内删除它们
我曾尝试使用HashSet复制、清除并复制回另一个数组列表，但我认为这只需要O(n)时间。
浏览 2提问于2012-07-25得票数 0
回答已采纳
假设我有两个列表，l1和l2。我想执行l1 - l2，它返回l1，其中删除了l2中的所有元素。
我可以想到一种天真的循环方法来做这件事，但那将是非常低效的。在c++中执行此操作的有效方法是什么？
浏览 0提问于2012-05-30得票数 3
回答已采纳
1回答
问题：
基本上，需要删除排序数组中的重复项而不创建新数组。我已经测试了我的解决方案，当相同数目的重复数为3、5、7(等等)时，它就会动摇。我能尝试什么技术？
浏览 4提问于2022-10-15得票数 -1
回答已采纳
1回答
我正在试图解决攀爬主板问题上的黑客等级。我的代码通过了除了测试用例6到9之外的所有测试用例，我假设测试用例使用的是大数据集。 return lo
elif arr[mid] < n:ret
浏览 0提问于2021-09-06得票数 0
回答已采纳
1回答
我想知道，在下面的标准和时间(可能是复杂的)下，会有这样的数据结构吗？如果我们获得一个未排序的列表L，就会生成一个数据结构，如下所示：
在O(lg n)下插入(y，S)，我们在结构S中<
浏览 0提问于2018-04-21得票数 0
回答已采纳
2回答
许多快速优先级队列(如和)都支持减键操作，该操作采用已存储在优先级队列中的元素，并有效地降低其优先级。在Fibonacci和配对堆的情况下，执行decrease key比从优先级队列中删除元素，然后重新插入它更快。
我想知道是否可以在有序字典结构(二进制搜索树、跳过列表等)上支持类似的操作。具体地说，假设我有一个有序的字典，并希望将某个键/值对的键更改为不同的</
浏览 5提问于2013-01-06得票数 8
回答已采纳
是的，我知道我发布了很多问题，但那是因为我要么需要保证我做得正确，我做错了什么，要么我完全没有头绪，在文档中找不到任何东西。不管怎样，遍历我的节点，并比较每个节点的文本(记录)，但是如果我有很多节点，这不是太耗时耗费内存了吗？有没有更好的方法来解决这个问题？如果我们有一些人有同样的问题，这里有一些工作代码，使用VST中的两个级别的节点！Parent
浏览 0提问于2011-01-15得票数 2
回答已采纳
3回答
假设我有一个文件，其中包含一组单词：2)如何按字母顺序返回这些单词？如果我选择哈希表，我知道1)解析所有单词的时间复杂度为O(n)，获得特定单词计数的时间复杂度为O(1)。
我不知道如何对哈希表进行排序，以及时间复杂度是多少。有什么帮助吗？
浏览 2提问于2013-02-07得票数 2
1回答
我很难找到以下声明的证据。证明没有基于比较的算法接收n个大小的数组并发射相同元素的数组，其中索引中的所有元素除以3，现在这些索引在线性时间内以它们的排序形式出现。例如，数组:8 6 1 3 0 9 4最初，元素8、3、4在数组中以3乘的索引形式出现，在执行算法之后，它们仍然以3乘的索引出现
浏览 0提问于2018-05-23得票数 1
回答已采纳
我有一个函数，它将网格中一系列点的所有邻居拉出到一定的距离，这涉及到许多重复项(我邻居的邻居再次== me )。
我已经尝试了几种不同的解决方案，但我不知道哪种更有效。下面的代码演示了两个并行运行的解决方案，一个使用std::vector sort- one erase，另一个使用std::copy into a std::unordered_set。我还尝试了另一种解决方案，那就是将包含邻居的向量传递给neighbour函数，该函数将使用std::f
浏览 1提问于2013-07-14得票数 4
回答已采纳
2回答
我有一个排列有序的N个元素数组，它们都分布在K个列表中，这也是排序的。什么是时间复杂性(以最严密的大-O符号)：
对于第二部分，我不确定(也许是O</e
浏览 0提问于2019-02-04得票数 0
回答已采纳
1回答
我有一个问题需要解决，但我想不出任何更简单、更重要的方法:快速解决。这有点像多旅行商问题的一部分。
首先，我有一个包含X行和N列的矩阵，N是我的算法的静态变量，而X是可变的。每条路由(= N )将被分成部分路由。这意味着，我有一个断点矩阵，其中包含X行和M (M < N)列。现在我的目标是从matrix中删除所有行，而部分路由是冗余
浏览 2提问于2011-12-11得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
