LeetCode 744. 寻找比目标字母大的最小字母

问题描述

给定一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。任务是返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。

解题思路

这个问题可以通过以下步骤解决：

1. 排序：首先，我们对 letters 数组进行排序，以确保它是按照非递减顺序排列的。

2. 遍历：然后，我们遍历排序后的数组，寻找第一个大于 target 的字符。

3. 返回结果：如果找到了这样的字符，我们返回它；如果没有找到，我们返回 letters 的第一个字符。

算法实现

以下是使用 C++ 语言实现的算法：

#include <vector>
#include <algorithm>

public:
    char nextGreatestLetter(std::vector<char>& letters, char target) {
        int n = letters.size();
        std::vector<char> sortedLetters = letters;
        std::sort(sortedLetters.begin(), sortedLetters.end());
        
        char s;
        for (int i = 0; i < n; i++) {
            if (sortedLetters[i] > target) {
                s = sortedLetters[i];
                break;
            }
        }
        
        if (s == '\0') {
            s = letters[0];
        }
        return s;
    }
};

代码分析

• 时间复杂度：O(n log n)，其中 n 是数组 letters 的长度。这是因为我们对数组进行了排序，排序的时间复杂度为 O(n log n)。

• 空间复杂度：O(n)，我们创建了一个额外的数组 sortedLetters 来存储排序后的字符。

结论

这个问题是一个典型的搜索问题，它要求我们在有序数组中找到满足特定条件的元素。通过排序和遍历，我们可以有效地解决这个问题。