如何查找重复字符

在云计算领域，查找重复字符是一个常见的问题，可以通过以下几种方法来实现：

使用哈希表：遍历字符串中的每个字符，将字符作为键存储在哈希表中，值为该字符出现的次数。最后再遍历哈希表，找到值大于1的字符即为重复字符。这种方法的时间复杂度为O(n)，空间复杂度为O(n)。
使用数组：由于ASCII字符的范围是0-127，可以创建一个大小为128的整型数组，将每个字符的ASCII码作为索引，统计每个字符出现的次数。最后再遍历数组，找到值大于1的索引即为重复字符。这种方法的时间复杂度为O(n)，空间复杂度为O(1)。
使用双重循环：遍历字符串中的每个字符，再嵌套一个循环遍历其后面的字符，判断是否有重复字符。这种方法的时间复杂度为O(n^2)，空间复杂度为O(1)。
使用集合：将字符串中的每个字符添加到一个集合中，如果添加失败则表示该字符已经存在，即为重复字符。这种方法的时间复杂度为O(n)，空间复杂度为O(n)。

以上是几种常见的查找重复字符的方法，根据具体的场景和需求选择合适的方法。在腾讯云中，可以使用云函数（SCF）来实现这些方法，具体可以参考腾讯云函数的文档：https://cloud.tencent.com/product/scf

如何去除时间为O(n)、空间为O(1)的单链表上的重复元素？

list、duplicates、singly-linked-list

如何去除时间为O(n)、空间为O(1)的单链表上的重复元素？元素可以是任何字符、数字，并且它们不会排序。例如，给定8 --> 6 --> 7 --> 6 --> 5 return 8 --> 6 --> 7 --> 5 O(1)空间看起来很难？

浏览 0提问于2013-08-19得票数 0

7回答

在O(N)时间内查找数组中的重复项

c++、algorithm

有没有办法在O(N)时间内找到N个元素组成的数组中所有重复的元素？示例：输入：11, 29, 81, 14, 43, 43, 81, 29 输出：29, 81, 43 对输入进行排序并进行线性扫描以检测重复项会破坏顺序，并给出输出: 29,43,81。按键排序另一个索引数组{0,1,...N-1}根据给定的数组获得{1,4,2}，然后对索引的结果集进行排序以获得{1,2,4}将得到{29,81,43}，但这需要O(N logN)时间。有没有一个O(N)算法来解决这个问题？附言:我忘了加一句:我不想使用哈希表。我正在寻找一个非散列的解决方案。

浏览 0提问于2011-10-01得票数 12

回答已采纳

1回答

更好的大O算法

algorithm、big-o

给出了一个n个整数的未排序数组，您希望找到数组中是否有任何重复项(即任何整数出现不止一次)。该算法基于大小为n个整数的未排序数组。使用嵌套循环来查找重复项，其复杂度为:O (N^2) 如果我们限制输入数据以实现一些最好的情况场景，那么如何限制输入数据以实现更好的大O复杂度？描述一种处理此有限数据的算法，以查找是否存在任何重复数据。什么是大O复杂性？这些问题提出以下问题：如何限制数据的一种方法。这将如何改变您查找重复项的算法，以及更好的大O复杂度是什么。我想出的答案是：如果我们将数据限制在5 (n = 5)的数组大小上，我们可以将复杂度降低到O(N)。如果数组是排序

浏览 1提问于2014-03-15得票数 0

2回答

如何为大型数据库置换搜索选择有效的算法？

algorithm、data-structures、hashmap、permutation

我的任务是编写Java代码，以便从数据库中读取行(其中可能有1000行)，并返回数据库中每一行的排列之和。例如，如果有3行这样的代码： ABCD BACD DCAB 那么输出应该是3 (ABCD == BACD，ABCD == DCAB，BACD == DCAB)，其中==的意思是‘是置换’。一个明显的答案是：(n =字典中的单词，m=word中的字符)：循环通过数据库(O(n)) 每一行：(O(1)) 按顺序排序(O(mlogm)) 添加到数组(O(1)) 循环通过数组(i = 0 : n) (O(n)) 循环通过数组(j = i + 1 : n)

浏览 0提问于2014-03-15得票数 0

1回答

扫描文本并检查它是否包含指定列表中的单词。

string、algorithm

要求目前，我们有一个包含一万多个关键字或句子的列表(数字是N)。输入是长字符串，长度是L。问:检查字符串中是否包含给定列表中的关键字或句子。这个问题可以用上的word过滤器来描述，但是我在那个页面上没有找到任何算法。解决这个问题的最简单的方法是迭代所有的关键字或句子，每次检查长文本是否包含这样的子字符串。由于我们有很多关键词，同时考虑到长的文本，性能也很差。它使用O(NL)时间似乎更好的解决方案应该在O(L)中完成。有人能给点建议吗？

浏览 4提问于2012-11-22得票数 2

回答已采纳

1回答

时间/空间复杂性

java、time-complexity、big-o、complexity-theory、space-complexity

准备考试。我认为时间复杂度是O(n^2)，空间复杂度是O(1)。请帮帮忙，我说的对吗？ public static String lastSubstring(String s) { int start=0; int end = start+1; int len =0; while (end + len < s.length()) { if (s.charAt(start + len) == s.charAt(end + len)) { len++; } else if (s.c

浏览 19提问于2020-11-02得票数 0

3回答

有效的Anagram空间复杂度

javascript、algorithm、big-o

浏览 0提问于2018-07-12得票数 2

3回答

在两个数组中计数相同的值

arrays、time-complexity、counting

给定两个大小为m的整数A和B的数组，取值范围为-n，n。我想要一个算法来计算A和B中有多少个公共值，如果一个值重复一次，例如: A={2,2,14,3}和B={1,2,14,14,5}，算法应该返回2。问题是我需要在O(m)时间内完成这个任务。我的尝试是创建一个大小为2n的C数组。并将A和B的所有值加n，并计算A的值: C[Ai]=1，需要O(m)时间，O(1)时间来创建数组。然后回顾B，数一数我在C中遇到了多少个1。到目前为止，这听起来不错，但是我一开始就不知道C中有什么，而且可能已经有一个1，这会错误地增加计数器，初始化C需要O(n)时间。有什么想法吗？先谢了。编辑:我得到

浏览 0提问于2019-08-25得票数 0

2回答

在x，y数组中找到两个数字，其中x<y，x至少重复n/3次，y至少重复n/4次。

java、arrays、algorithm、data-structures、time-complexity

我一直在努力解决一个线性时间的数组问题，问题是:假设给我们一个数组A1.n编写一个返回true的算法，如果:数组x中有两个数字，y中有以下两个数字： X<y X重复次数超过n/3次 Y重复次数超过n/4次。假设我们有一个排序数组，我已经尝试编写了下面的java程序，但我不认为它是最好的实现。 public static boolean solutionManma(){ int [] arr = {2,2,2,3,3,3}; int n = arr.length; int xCount = 1; int yCount = 1;

浏览 7提问于2022-03-26得票数 0

8回答

一种在固定空间和O(n)时间内查找重复条目的算法

c++、algorithm

给定一个N个整数的数组，使得只有一个整数重复。在O(n)时间和常量空间中找到重复的整数。整数的值或N的值没有范围例如，假设一个由6个整数组成的数组为23 45 67 87 23 47。答案是23 (我希望这涵盖了模棱两可和含糊的部分) 我在网上搜索，但找不到任何这样的问题，其中整数的范围是不固定的。另外，是一个回答了我类似问题的例子，但在这里，他创建了一个哈希表，其中包含C++.But中最高的整数值，cpp不允许这样创建一个包含2^64元素的数组(在64位计算机上)。很抱歉我没有在数组是不可变的之前提到它

浏览 1提问于2011-11-25得票数 8

回答已采纳

4回答

查找在数组中出现m次的唯一整数

arrays、algorithm

这个数组中的所有其他整数都出现了n次。我们有n>m。此数组中的所有元素都是整数。你能设计一种在O(N)中工作的算法吗？N是数组中元素的数量，同时最小化空间复杂度？在最好的情况下，空间复杂度可以限制为O(log(m))。一个特例是n=2和m=1 (这很简单)。有没有可以处理任意m和n的通用算法？谢谢

浏览 0提问于2014-12-29得票数 0

1回答

创建一个将用给定字符替换所有重复字符的方法。方法签名将是replaceRepeating(String，char)

string、replace

创建一个将用给定字符替换所有重复字符的方法。方法签名将是replaceRepeating(String，char)。例如，如果我调用replaceRepeating(“Krishnan”，‘’)，输出应该是“K__sh*vd”。重复的字符是r，i，n和a，它们都被*替换了。

浏览 6提问于2020-05-30得票数 0

3回答

降低这两种方法的时间复杂度？

java、algorithm

/* * Returns true if this and other are rankings of the same * set of strings; otherwise, returns false. Throws a * NullPointerException if other is null. Must run in O(n) * time, where n is the number of elements in this (or other). */ public boolean sameNames(Ranking other) { ArrayList<

浏览 2提问于2014-02-24得票数 0

5回答

哈希表运行时复杂性(插入、搜索和删除)

algorithm、data-structures、hash、time-complexity、hashtable

为什么我总是在哈希表上看到这些函数的运行时复杂性不同？在wiki上，搜索和删除是O(n) (我认为哈希表的重点是不断查找，所以如果搜索是O(N)，那还有什么意义)。在不久前的一些课程笔记中，我看到了广泛的复杂性，这取决于某些细节，包括全为O(1)的一个。如果我可以得到所有的O(1)，为什么还要使用其他实现呢？如果我在C++或Java这样的语言中使用标准哈希表，我能期望的时间复杂度是多少？

浏览 1提问于2012-02-10得票数 92

回答已采纳

12回答

查找2个字符串在O(1)空间和O(n)时间内是否为字形

algorithm、anagram

在O(nlogn)时间内对两个字符串进行排序后，您可以发现这两个字符串是否为字形，但是否可以在o(n)时间和O(1)空间中找到它。

浏览 0提问于2011-07-11得票数 4

6回答

确定在O(n)时间和O(1)空间中发生最多的元素

java、c、algorithm

让我首先说，这不是一个家庭作业问题。我正在尝试设计一个缓存，其驱逐策略依赖于缓存中发生最多的条目。在软件方面，假设我们有一个具有不同元素的数组，我们只想找到发生最多的元素。例如：{1, 2 ,2,5,7,3,2,3}应该返回2，因为我使用的是硬件，所以朴素的O(n^2)解决方案需要巨大的硬件开销。使用哈希表的更聪明的解决方案对于软件很有效，因为哈希表的大小可能会改变，但在硬件中，我将有一个固定大小的哈希表，可能不会太大，因此冲突会导致错误的决策。我的问题是，在软件中，我们能否在O(n)时间复杂度和O(1)空间内解决上述问题？

浏览 10提问于2014-04-24得票数 12

回答已采纳

2回答

如何寻找和k的最大子阵

arrays、algorithm、data-structures、sliding-window、sub-array

假设你给出了一个N的数组，它可以有正数和负数。我们需要返回等于k的最大子数组的长度。我尝试使用滑动窗口算法，但很快我发现它在这里不能工作，因为数组元素可以有正负整数。例如： arr=-20，-38，-4，-7,10,4和k =3很明显，有两个可能的子阵列(-4，-7，10和-7,10)，其和等于给定的k，因此输出将是4(最大子阵的长度) 蛮力法采用O(n^2)法，是否有更好的方法来解决同样的问题？

浏览 4提问于2022-10-05得票数 0

3回答