编写反向字符串O(N)时间复杂度和O(N)空间复杂度的程序

Question

我被要求解决低于N ^ 2时间复杂度和O(N)空间复杂度的以下问题:

为以下情况编写程序反向字符串:

输入: - "Hello World"输出: - "olleH dlroW"

我试图弄清楚它,但无论我尝试什么,我都无法想出时间复杂度低于N ^ 2,我的代码可以在下面看到,你有什么建议我怎么能想出来线性时间的解决方案？

注意:不允许使用内置方法

 public static String stringReverser(String str) {
        if (str == null || str.isEmpty()) {
            throw new IllegalArgumentException();
        }
        if (str.length() < 2) {
            return str;
        }
        String[] strArr = str.split(" ");
        StringBuffer newHolder = new StringBuffer();
        for (int i = 0; i < strArr.length; i++) {
            int j = 0;
            int len = strArr[i].length();
            char[] newCharStr = strArr[i].toCharArray();
            while (j < len) {
                char temp = newCharStr[j];
                newCharStr[j] = newCharStr[len - 1];
                newCharStr[len - 1] = temp;
                len--;
                j++;
            }
            newHolder.append(String.valueOf(newCharStr));
            if(i != strArr.length-1){
                newHolder.append(" ");
            }
        }

        return newHolder.toString();
    }

Answer 1

看起来你想要反转字符串中的单词,而不是整个字符串.干得好:

public static String reverseWords(String str)
{
    char[] chars = str.toCharArray();
    int wstart=0;
    for (int pos=0;;pos++)
    {
        if (pos < chars.length && chars[pos]!=' ')
        {
            continue;
        }
        for (int wend=pos-1; wend>wstart; ++wstart,--wend)
        {
            char t=chars[wstart];
            chars[wstart]=chars[wend];
            chars[wend]=t;
        }
        if (pos>=chars.length)
        {
            break;
        }
        wstart=pos+1;
    }
    return String.valueOf(chars);
}

这是您可以找到的最快,最节省空间的版本.如果这是家庭作业,你的教授会知道你没有写它:)

但是,你在问题中写的那个满足了要求--O(N)时间和O(N)空间 - 所以你可能想要转入那个.恭喜!

因为你似乎认为它需要O(N ^ 2)时间,所以时间是如何分解的:

• str.split:O(输出数组的大小+输出字符串的大小)= O(str.length()),即O(N)
• 迭代词:O(单词数)= O(N)
• 创建和反转单词字符串:每个O(单词大小),总O(N)
• newHolder.append:O(创建的字符串的总大小)= O(str.length())= O(N)
• newHolder.toString():O(输出大小)= O(N)

所以,5*O(N)= O(N) - 你很高兴.