给定字符数组，在一次传递中找到第k个非重复字符
问题描述 投票：1回答：9
例如。 bacdbecdfb
第一个非重复的字符是'a'，第二个是'e'。
这是一个面试问题，我想出了使用哈希来解决2次传球但面试官想要一次通过。他给出的提示是k的最大值可以是26。
9个回答
投票
你只有26个可能的角色，所以你可以创建一个大小为26的int数组，这样你就可以找到所有不重复的字符（通过遍历你的输入并增加相关的字符数）。需要另一次迭代来找到它们的顺序（也可以在第二次迭代中重复或不重复，在第一次迭代中你只需设置字符的数字，例如a在位置0并且看到1次）。
这称为计数排序。
编辑：为了在一个路径中执行此操作，您需要向排序数据添加额外信息，实际上您应该添加第一个访问时间，因此您将拥有struct数组：
struct data
{
int firstVisitedPosition;
int visitedCount;
}
data[26] sorter = new data[26];// --> initialize it as the way said above.
//Find all items in sorter with visitedCount=1
var justOnes = sorter.Where(x=>x.visitedCount == 1).ToList();
Find minimum firstVisitedPosition:
var minPos = justOnes.Min(x=>x.firstVisitedPosition);
var minItem = justOnes.First(x=>x.firstVisitedPosition == minPos);
小心sorter长度为26，而justOnes长度≤26，因此迭代它们100次与输入数据迭代无关并且没有问题，排序或其他操作都是常量。
投票
下面是C中的解决方案。请注意，输入字符串仅解析一次。
编辑：考虑输入：“bacdbecdfb”在解析之前，charIndex设置为0
迭代1：[b] acdbecdfb
'b'的位置递增计数1.我使用charCnt按字母顺序存储输入字符串中所有字符的出现次数。 charCnt中'b'的索引是1.（0表示a，1表示b，依此类推）
同样，当我们发现一个新的char时，我们需要记录它，因为最终输出取决于输入字符串中字符的排序。所以我把'b'的位置放在charIndex中。即。 charIndex [0] = 1
charCnt = {0,1,0,0，....} charIndex = {1,0,0，....}
下一次迭代：b [a] cdbecdfb
'a'在charCnt中的位置递增计数1.我们第一次看到'a'，所以在charIndex中存储索引。
charCnt = {1,1,0,0，....} charIndex = {1,0,0，....}
下一次迭代：ba [c] dbecdfb
'c'在charCnt中的位置的增量计数为1.我们第一次看到'c'，所以在charIndex中存储索引。
charCnt = {1,1,1,0，....} charIndex = {1,0，2,0,0，....}
下一次迭代：bac [d] becdfb
'b'在charCnt中的位置递增计数为1.我们第一次看到'd'，所以将索引存储在charIndex中。
charCnt = {1,1,1,1,0,0，....} charIndex = {1,0，2,3,0，....}
下一次迭代：bacd [b] ecdfb
'b'在charCnt中的位置的增量计数为1.我们之前看过'b'所以不要更新charIndex。
charCnt = {1,2,1,1,0,0，....} charIndex = {1,0，2,3,0，....}
你可以继续相同的其余字符串。
最后，你会得到
charCnt = {1,3,2,2,1,1,0,0，......} charIndex = {1,0，2,3,4,5,0,0 ......
第二个for循环是扫描charIndex并找出charCnt中有多少相应的元素计数1.在得到第k个这样的条目后，我们得到所需的字符。
char FindKthNonRepetitiveCharacter(char *string, int strlen, int k)
{
int charCnt[26]; // stores the count of ewach character a,b,c,..
// in the input string
int charIndex[26]; // stores the index for the character discovered
// in input string to refer to charCnt
int i,charIndexCnt = 0;
for (i = 0; i < 26; i++) { // init
charCnt[i] = charIndex[i] = 0;
}
for (i = 0; i < strlen; i++) {
int index = string[i] - 'a';
++charCnt[index];
if(charCnt[index] == 1) { // only add newly discovered char.
charIndex[charIndexCnt] = index;
charIndexCnt++;
}
}
for (i = 0; i < charIndexCnt && k > 0; i++) {
if (charCnt[charIndex[i]] == 1)
k--;
}
return (charIndex[i-1] + 'a');
}
投票
使用存储对的数组：字符以及到目前为止在字符串中出现的次数。因此，对于您演示所有步骤的示例：
[b]acdbqcdfb -> [(b, 1)]
b[a]cdbqcdfb -> [(b, 1), (a, 1)]
ba[c]dbqcdfb -> [(b, 1), (a, 1), (c, 1)]
bac[d]bqcdfb -> [(b, 1), (a, 1), (c, 1), (d, 1)]
bacd[b]qcdfb -> [(b, 2), (a, 1), (c, 1), (d, 1)]
bacdb[q]cdfb -> [(b, 2), (a, 1), (c, 1), (d, 1), (q, 1)]
bacdbq[c]dfb -> [(b, 2), (a, 1), (c, 2), (d, 1), (q, 1)]
bacdbqc[d]fb -> [(b, 2), (a, 1), (c, 2), (d, 2), (q, 1)]
bacdbqcd[f]b -> [(b, 2), (a, 1), (c, 2), (d, 2), (q, 1), (f, 1)]
bacdbqcdf[b] -> [(b, 3), (a, 1), (c, 2), (d, 2), (q, 1), (f, 1)]
请注意，您不是按字典顺序添加字母，而是按照外观顺序添加，因此我需要稍微修改您的示例。最后，您传递一次最终数组并计算出现顺序出现的所有字母。你的答案是第k个。此解决方案仅在整个数组中传递一次，并且每个字母也会遍历一次字母出现的数组。因此，您支付26 * n，其中n是数组的长度。然而，这个解决方案正在进行一次通过，但并不比你的好。如果您有一个长度为26的单独数组，并且在每个字母的辅助数组中存储索引，则可以提高此复杂性。这是最后这个第二个数组的例子：a - 1, b - 0, c -2, d - 3. e - null, f - 5, g - null........q - 4, r - null...。该阵列使您能够在单个操作中找到所需的索引，将解决方案优化为n。
投票
这个怎么样。
string s = "bacdbecdfb";
List<char> nonRepeatedlist = new List<char>();
List<char> repeatedList = new List<char>();
foreach (char c in s)
{
if (!nonRepeatedlist.Contains(c) && !repeatedList.Contains(c))
{
nonRepeatedlist.Add(c);
}
else
{
nonRepeatedlist.Remove(c);
repeatedList.Add(c);
}
}
if (k < nonRepeatedlist.Count)
return nonRepeatedlist[k - 1];
投票
import java.util.LinkedList;
import java.util.List;
public class kthnonrepetitive
{
public static void main(String argfs[])
{
boolean[] bool = new boolean[256];
List<Character> list = new LinkedList<Character>();
String s = "TOTALALZOXYX";
for(int i=0;i<s.length();i++)
{
char c = s.charAt(i);
if(bool[c])
{
list.remove(Character.valueOf(c));
}
else
{
bool[c]=true;
list.add(Character.valueOf(c));
}
}
System.out.println(list.toArray()[1]);
}
}
上面的程序打印字符串中的第二个唯一字符。如果您发现上述程序有任何问题，请告诉我。
投票
我会在Java中使用LinkedHashSet来跟踪仅出现一次的字符。对于初始字符串的每个元素，如果未找到，则将其添加到集合中;如果已在集合中，则将其删除。在遍历初始字符串之后，将该组唯一字符迭代到第k个元素。
投票
这是一种在单次传递中找到第k个唯一字符的算法。它需要空间O（n）。
unique_count := 0; // a variable to count unique character found so far
node *head := NULL; // head of the list
node *tail := NULL;
hashmap<char, node*> map; // This contains the mapping for characters when unique_count >= k
int input[26];
for( int i = 0; i < n; i++)
{
if (input[c % 26] == 0) // This char is first time appeared
{
unique_count++;
if ( unique_count < k)
{
input[c % 26] += 26;
continue;
}
//we found the kth unique chars so far, but it might not be, so store it in list
else if (unique_count == k)
{
node *n = new node(c);
head = n;
tail = n;
}
else
{
node *n = new node(c);
tail->next = n;
n->prev = tail;
tail = n;
map[c] = n;
}
input[c % 26] += 26;
}
else if( input[ c % 26] < 26)// This is 2nd time this char has appeared
{
if ( unique_count < k)
unique_count--;
else if ( unique_count == k)
{
delete(head);
head = tail = NULL;
unique_count --;
}
else
{
// delete that node
node *temp = map[c];
if (temp == tail)
{
tail->prev->next = NULL;
tail = tail->prev;
}
else
{
temp -> prev->next = temp->next;
temp->next->prev = temp->prev;
}
delete(temp);
unique_count--;
}
input[c % 26] += 26;
}
// This is 3rd or more time this character has appeared. don't add to avoid integer overflow
//end for loop
}
if ( head == NULL) return head->data;
else "No kth unique character"
投票
我们甚至可以在O（n）中运行流（按发生顺序排列第k）
有两种数据结构：
- 哈希映射：存储已访问过的号码。
- 双向链表：存储号码的顺序
哈希映射将指向双链表中相应数字的节点。
我们可以想到以下算法：
- 如果哈希映射中不存在当前号码（即不重复号码），则在哈希映射中标记所访问的号码，并将号码添加到链接列表。 （保持指向DLL的tail和kth指针）
- 在计数器变为'k'时，保持DLL中数字的计数器指向尾的'kth'指针。
- 如果当前的数字存在于Hash Map中并且指向DLL中的节点，我们必须从DLL中删除相应的节点，（因为我们已经访问了数字而必须保持哈希映射中的值，我们需要记住它）。 一世。如果从DLL中删除的数字小于'kth'指向的数字，则将'kth'指针增加1。 II。如果要删除的数字大于'kth'指针指向的数字，则不需要做任何事情（保持'kth'指针指向的位置）。
'kth'指针将始终指向正在运行的流中的'kth'非重复数字。
由于流中的数字是有限的，因此散列将具有已知的有限大小。
投票
一个包含所有场景的解决方案但在python中：#Program返回给定字符串中的第k个非重复字母。
class RepeatingOrNot(object):
@classmethod
def non_repeating(cls, my_str, k):
my_list = list(my_str)
repeating = []
non_repeating = list()
for i in range(len(my_list)):
if my_list[i] in repeating:
continue
else:
for j in range(i+1, len(my_list)):
if my_list[i] == my_list[j]:
repeating.append(my_list[i])
break
else:
non_repeating.append(my_list[i])
continue
if non_repeating:
if not len(non_repeating) < k:
return "The {0}th non-repeating letter in the " \
"input string is {1}".format(k, non_repeating[k - 1])
else:
return "There are not as many repeating characters in the" \
" input string as user expected. " \
"Please enter a valid value for k"
else:
return "The string does not have a single unique character." \
"Please try a different string"
my_str = "ataaaaataaaaaaaaaaqwetaaataattttaaaaatttaaaarf"
my_str1 = "abcdefghijklmnopqrstuvwxyz"
my_str2 = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
my_str3 = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz12345678$9abcljldjljlauoejrlkjdljf "
if __name__ == "__main__":
test_obj = RepeatingOrNot()
print test_obj.non_repeating(my_str, 5)
print test_obj.non_repeating(my_str, 15)
print test_obj.non_repeating(my_str1, 25)
print test_obj.non_repeating(my_str1, 29)
print test_obj.non_repeating(my_str2, 4)
print test_obj.non_repeating(my_str3, 9)
最新问题
- Azure Application Insights 不显示 C# ILogger 日志
- 在 PyQt5 中将主行计数器作为第一列/文本添加到 QTreeView 中？
- 找不到模块：错误：无法解析“framework7/lite-bundle”
- 连接两个时间戳不相同的 MySQL 表
- CSH 中双引号反引号内变量扩展（文件名）的正确引用是什么？
- `metal-cpp` 头文件
- Flutter sdk 错误'（退出代码：1 pub 输出的最后一行：“因为 Room_Booking 需要 SDK 版本 >=3.4.0 <4.0.0, version solving failed." )
- 鼠标悬停多个 td rowspan
- 如何剪辑 Path2D？
- 如何从我的插件访问 Eclipse Servers 插件
- 带有外部存储器迭代器的XGBoost AFT生存模型
- 如何在Vscode中的bash终端上运行python文件？
- 查询将查找与 user2 发布相同标记集的用户
- 如何将 Telegram 聊天机器人与 React 网站聊天小部件连接？
- 在 Firebase 实时回收器视图中仅过滤和加载非重复名称
- ggplot 切断州边界线
- TryTake 正在窃取最近在另一个线程上添加的元素
- numpy.random.randn 每次都会生成相同的值
- 在 Windows 上使用 GSL（编译、链接等）。分步指南
- 查询规划器未使用时间戳上的部分索引，尽管 WHERE 子句中的周期匹配