有效地反转字符数组中单词(而不是字符)的顺序
给定一个组成单词句子的字符数组,给出一个有效的算法来反转其中单词(而不是字符)的顺序。
输入和输出示例:
>>> reverse_words("this is a string")
'string a is this'
应该是 O(N) 时间和 O(1) 空间(不允许 split() 和压入/弹出堆栈)。
该谜题取自此处。
Given an array of characters which forms a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.
Example input and output:
>>> reverse_words("this is a string")
'string a is this'
It should be O(N) time and O(1) space (split()
and pushing on / popping off the stack are not allowed).
The puzzle is taken from here.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(21)
@Daren Thomas
在 D(数字火星)中实现算法(时间 O(N),空间 O(1)):
输出:
@Daren Thomas
Implementation of your algorithm (O(N) in time, O(1) in space) in D (Digital Mars):
Output:
在伪代码中:
In pseudo code:
您将使用所谓的迭代递归函数,该函数在时间上为 O(N),因为它需要 N(N 是单词的数量)次迭代才能完成,在空间上为 O(1),因为每次迭代都在其中保存自己的状态函数参数。
注意:我已经在方案中编写了这个,我是一个完全的新手,因此对于缺乏正确的字符串操作表示歉意。
remove-first-word 找到句子的第一个单词边界,然后获取该字符部分(包括空格和标点符号)并删除它并返回新句子
add-first-word 找到句子的第一个单词边界,然后取出该部分字符(包括空格和标点符号)并将其添加到反向句子中并返回新的反向-句子内容。
You would use what is known as an iterative recursive function, which is O(N) in time as it takes N (N being the number of words) iterations to complete and O(1) in space as each iteration holds its own state within the function arguments.
Note: I have written this in scheme which I am a complete novice, so apologies for lack of correct string manipulation.
remove-first-word finds the first word boundary of sentence, then takes that section of characters (including space and punctuation) and removes it and returns new sentence
add-first-word finds the first word boundary of sentence, then takes that section of characters (including space and punctuation) and adds it to reverse-sentence and returns new reverse-sentence contents.
Python 中空间 O(N) 和时间 O(N) 的解决方案:
O(N) in space and O(N) in time solution in Python:
这是我的答案。 没有库调用,也没有临时数据结构。
Here is my answer. No library calls and no temp data structures.
将字符串压入堆栈,然后将其弹出 - 这仍然是 O(1) 吗?
本质上,这与使用 split() 相同...
O(1) 不是意味着就地吗? 如果我们只需附加字符串和其他内容,这个任务就会变得很容易,但这会占用空间...
编辑:Thomas Watnedal 是对的。 以下算法的时间复杂度为 O(n),空间复杂度为 O(1):
我想我们需要证明步骤 2 实际上只是 O(2n)...
pushing a string onto a stack and then popping it off - is that still O(1)?
essentially, that is the same as using split()...
Doesn't O(1) mean in-place? This task gets easy if we can just append strings and stuff, but that uses space...
EDIT: Thomas Watnedal is right. The following algorithm is O(n) in time and O(1) in space:
I guess we would need to prove that step 2 is really only O(2n)...
C/C++ 中的解决方案:
时间复杂度为 O(n),空间复杂度 O(1)。
编辑:稍微清理一下。
第一次遍历字符串显然是 O(n/2) = O(n)。 第二遍是 O(n + 所有单词的总长度 / 2) = O(n + n/2) = O(n),这使得这是一个 O(n) 算法。
A solution in C/C++:
This should be O(n) in time and O(1) in space.
Edit: Cleaned it up a bit.
The first pass over the string is obviously O(n/2) = O(n). The second pass is O(n + combined length of all words / 2) = O(n + n/2) = O(n), which makes this an O(n) algorithm.
注意:句子必须以 点(.) 结尾
因为 NULL 字符不会自动分配
在句子的末尾*
NOTE: Sentence must end with dot(.)
because NULL character is not assigned automatically
at the end of the sentence*
将每个单词压入堆栈。 将所有单词从堆栈中弹出。
Push each word onto a stack. Pop all the words off the stack.
编辑:我想我应该阅读整个问题......继续。
edit: i guess i should read the whole question... carry on.
就我的时间而言,效率很高:用 REBOL 写了不到 2 分钟:
尝试一下:
verse_words“这是一个字符串”
“字符串a是这个”
Efficient in terms of my time: took under 2 minutes to write in REBOL:
Try it out:
reverse_words "this is a string"
"string a is this"
C++ 解决方案:
A C++ solution:
Ruby 解决方案。
A Ruby solution.
在 C# 中,就地、O(n) 并经过测试:
in C#, in-place, O(n), and tested:
这个问题可以用时间 O(n) 和空间 O(1) 来解决。 示例代码如下所示:
This problem can be solved with O(n) in time and O(1) in space. The sample code looks as mentioned below:
单线:
输出:
A one liner:
Output:
解决这个问题的算法基于两步过程,第一步将反转字符串中的各个单词,然后第二步反转整个字符串。 算法的实现将花费 O(n) 时间复杂度和 O(1) 空间复杂度。
The algorithm to solve this problem is based on two steps process, first step will reverse the individual words of string,then in second step, reverse whole string. Implementation of algorithm will take O(n) time and O(1) space complexity.
在 C 中:(C99)
给出输出:
这最多需要 4N 时间,并且常数空间很小。
不幸的是,它不能优雅地处理标点符号或大小写。
In C: (C99)
This gives output:
This takes at most 4N time, with small constant space.
Unfortunately, It doesn't handle punctuation or case gracefully.
在红宝石中
in Ruby