时间戳

首页 > 解决方案 > 在不到 o(n^2) 的时间内使用常数空间交换 char* 中的两个单词

string - 在不到 o(n^2) 的时间内使用常数空间交换 char* 中的两个单词

问题描述

给一个字符串一个 char*，比如包含“hellosir”，以及每个单词的长度，如何在小于 o(n^2) 的时间内使用常量空间返回一个包含“sirhello”的 char*？（我在一次技术面试中被问到这个问题）

函数签名：

char* swapWords(char* str, int firstWordLen, int secondWordLen);

在“hellosir”示例中，firstWordLen 为 5，secondWordLen 为 3。

谢谢

标签： stringcharc-strings

解决方案

char* swapWords(char* str, int firstWordLen, int secondWordLen) {
    char* newStr = (char*) malloc(sizeof(char) * (firstWordLen + secondWordLen + 1));
    for(int i = 0; i < secondWordLen; i++) {
        newStr[i] = str[firstWordLen + i];
    }
    for(int i = 0; i < firstWordLen; i++) {
        newStr[secondWordLen + i] = str[i];
    }
    newStr[firstWordLen + secondWordLen] = 0;
    return newStr;
}

解释：

  • 循环第二个单词，它从第一个单词的末尾开始，所以 firstWordLen + i，并将字符放在新字符数组的开头
  • 循环第一个单词，所以从 0 到 firstWordLen 并将它放在之前放置的第二个单词的末尾，所以在 secondWordLen + i
  • 由于空终止，将 0 添加到新 char 数组的末尾

Ah ok, this is not constant space my bad，速度是O(n)，但是空间也是O(n)

推荐阅读