查找在O（n）的使用布尔数组的第一个非重复一串字符？ [英] Finding the first non-repeated character of a string in O(n) using a boolean array?

问题描述

我的问题是有关这个问题的前面

My question is related to this earlier question

<一个href="http://stackoverflow.com/questions/2285533/find-the-first-un-repeated-character-in-a-string">Find第一个非重复字符的字符串。

在我的一次采访中，我被要求写一个函数用作为额外的空间长度为n的只是一个布尔数组，以确定时间为O（n）的字符串的第一个独特的性格。也就是说，发现在一个字符串仅使用O（n）的复杂性和长度为n的布尔数组的第一个非重复的字母。可有人建议如何与布尔阵列解决呢？

In one of my interviews I was asked to write a function to determine the first unique character in a string in time O(n) using as extra space only a boolean array of length n. That is, find the first non repeating letter in a string using only O(n) complexity and a bool array of length n. Can some suggest how to solve it with bool array?

推荐答案

那么，如果字符集的大小是不变的......说，例如，0-255 ...

Well, if the size of the character set is constant... Say, for instance, 0-255...

扫描字符串寻找字符0。

Scan the string looking for character 0.

然后扫描字符串寻找字符1。

Then scan the string looking for character 1.

然后扫描字符串寻找字符2。

Then scan the string looking for character 2.

...

最后，扫描字符串寻找字符255。

Finally, scan the string looking for character 255.

这需要256 * n个操作这是O（n）。

This takes 256*n operations which is O(n).

在每次扫描时，如果字符是唯一的，其标记位图中的位置。在结束返回在第一标记的位置的字符。 （或只记录第一个独特的性格和它的位置用K +的log（n）位使用硬codeD查找表或任何对非常小的N;。否则，n位是大手笔）

During each scan, if the character is unique, mark its position in the bitmap. At the end return the character at the first marked position. (Or just record the first unique character and its location using k + log(n) bits. Use a hard-coded lookup table or whatever for very small n; otherwise, n bits is generous.)

虽然不知何故，我怀疑这是不是面试官脑子里想的是什么。

Although somehow I suspect this is not what the interviewer had in mind.

这篇关于查找在O（n）的使用布尔数组的第一个非重复一串字符？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！