我正在尝试解决有关Pramp的问题:
实现功能reverseWords,以最有效的方式反转数组中单词的顺序。
例如:arr = ['p','e','r','f','e','c','t','','m','a','k','e ','s',',','p','r','a','c','t','i','c','e']
输出:['p','r','a','c','t','i','c','e',',','m','a','k', 'e','s',',','p','e','r','f','e','c','t']
他们提供的类似Python的伪代码如下:
function reverseWords(arr):
# reverse all characters:
n = arr.length
mirrorReverse(arr, 0, n-1)
# reverse each word:
wordStart = null
for i from 0 to n-1:
if (arr[i] == ' '):
if (wordStart != null):
mirrorReverse(arr, wordStart, i-1)
wordStart = null
else if (i == n-1):
if (wordStart != null):
mirrorReverse(arr, wordStart, i)
else:
if (wordStart == null):
wordStart = i
return arr
# helper function - reverses the order of items in arr
# please note that this is language dependent:
# if are arrays sent by value, reversing should be done in place
function mirrorReverse(arr, start, end):
tmp = null
while (start < end):
tmp = arr[start]
arr[start] = arr[end]
arr[end] = tmp
start++
end--
他们说时间复杂度为O(n),这主要是因为他们两次遍历数组,并且每一项的动作数均恒定。碰巧的是,我想出了stringstreams
在C ++中使用的完全相同的方法,但是认为它效率不高!
我认为此代码段的时间复杂度应为O(mn),其中m
字符串中的单词n
数和每个单词中字母的平均数。之所以如此,是因为我们遍历了输入中的所有元素,并且在最坏的情况下mirrorReverse()
,对于给定的,再次访问所有元素进行反转i
。
哪个是对的?
在O(n)中,n
是指输入的长度(总字符),而不是单词的数量。我怀疑您感到困惑,因为代码n
在后一种意义上使用了变量。
注意说明:“遍历数组...”。“数组”由单个字符组成。
对我来说,实现似乎有点愚蠢。更具可读性:
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句