代码时间复杂度分析：Pramp平台reverseWords高效实现问题求解

Let's break down how to solve this problem with optimal time and space complexity. The task is to reverse the order of words in a character array (where words are separated by single spaces) without using excessive extra space.

Approach: Two-Pass In-Place Reversal #

The most efficient way to do this is with a two-step in-place reversal strategy, which gives us O(n) time complexity and O(1) space complexity (no extra data structures needed beyond a few temporary variables):

1. Reverse the entire array first: This flips the order of all characters, which reverses the word order but also reverses each individual word.
2. Reverse each individual word: Go through the array again, and reverse the characters within each word to fix their internal order.

Example Walkthrough #

Let's use the sample input to see how this works:

• Original array: ['p','e','r','f','e','c','t',' ','m','a','k','e','s',' ','p','r','a','c','t','i','c','e']
• Step 1: Reverse the entire array → ['e','c','i','t','c','a','r','p',' ','s','e','k','a','m',' ','t','c','e','f','r','e','p']
• Step 2: Reverse each word:
  • Reverse ['e','c','i','t','c','a','r','p'] → ['p','r','a','c','t','i','c','e']
  • Skip the space, reverse ['s','e','k','a','m'] → ['m','a','k','e','s']
  • Skip the space, reverse ['t','c','e','f','r','e','p'] → ['p','e','r','f','e','c','t']
• Final result: ['p','r','a','c','t','i','c','e',' ','m','a','k','e','s',' ','p','e','r','f','e','c','t'] (matches the sample output)

Implementation (Python-like Pseudocode) #

Here's how to translate this approach into code:

def reverseWords(arr):
    # Helper function to reverse a subarray from index start to end (inclusive)
    def reverse_subarray(start, end):
        while start < end:
            # Swap characters at start and end
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1
    
    # Step 1: Reverse the entire array
    reverse_subarray(0, len(arr) - 1)
    
    # Step 2: Reverse each individual word
    word_start = 0
    for i in range(len(arr) + 1):
        # When we hit a space or the end of the array, reverse the current word
        if i == len(arr) or arr[i] == ' ':
            reverse_subarray(word_start, i - 1)
            word_start = i + 1
    
    return arr

Complexity Analysis #

• Time Complexity: O(n). We traverse the array twice (once for full reversal, once for word-wise reversal), and each character is swapped a constant number of times.
• Space Complexity: O(1). All operations are done in-place; we only use a few variables for indices and swapping.

Why This Is Better Than Other Approaches #

Alternative methods (like converting the array to a string, splitting into words, reversing the word list, then converting back to an array) require O(n) extra space to store the list of words. The two-pass in-place reversal avoids this, making it the most memory-efficient solution for large input arrays.

内容的提问来源于stack exchange，提问作者J. Doe