当前位置：首页 > article >正文

力扣中等题——顺次数

article 2025/1/24 2:12:21

题目链接：1291. 顺次数 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。

请你返回由 [low, high] 范围内所有顺次数组成的有序列表（从小到大排序）。

示例

示例 1：

输出：low = 100, high = 300
输出：[123,234]

示例 2：

输出：low = 1000, high = 13000
输出：[1234,2345,3456,4567,5678,6789,12345]

提示：

10 <= low <= high <= 10^9

解法一：面向测试用例编程

该方法的实现是通过预定义一个包含所有顺序数字的数组，遍历该数组并根据给定的范围条件筛选出合适的数字，最后返回这些数字。
由于顺序数字的数量有限，使用这种预定义的方式可以在时间复杂度上非常高效，避免了动态生成顺序数字的复杂计算。

Java写法：

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        // 这里定义了一个整型数组 arr，包含了所有可能的顺序数字。
        // 顺序数字的特点是由连续的数字组成，且不能跨越数字（如：不可以是 1, 3, 4 这样的组合）。
        int[] arr = {12, 23, 34, 45, 56, 67, 78, 89, 
        123, 234, 345, 456, 567,678, 789, 1234, 2345, 
        3456, 4567, 5678, 6789,12345, 23456, 34567, 
        45678, 56789, 123456, 234567, 345678,456789, 
        1234567, 2345678, 3456789, 12345678, 23456789, 123456789};
        // 创建一个 ArrayList 用于存储满足条件的顺序数字。
        List<Integer> list = new ArrayList<>();
        
        // 检查它是否在指定的范围 [low, high] 内
        for(int num:arr){
            if(low <= num && num <= high){
                list.add(num);
            }
        }
        return list;
    }
}

运行时间

C++写法：

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        // 定义一个数组，包含所有可能的顺序数字
        int arr[] = {12, 23, 34, 45, 56, 67, 78, 89, 
                      123, 234, 345, 456, 567, 678, 789, 
                      1234, 2345, 3456, 4567, 5678, 6789, 
                      12345, 23456, 34567, 45678, 56789, 
                      123456, 234567, 345678, 456789, 
                      1234567, 2345678, 3456789, 12345678, 
                      23456789, 123456789};
        
        // 创建一个 vector 用于存储满足条件的顺序数字
        vector<int> list;
        
        // 检查它是否在指定的范围 [low, high] 内
        for (int num : arr) {
            if (low <= num && num <= high) {
                list.push_back(num);
            }
        }
        
        return list;
    }
};

运行时间

时间复杂度和空间复杂度

解法二：常规写法枚举

外层循环 (for (int i = 1; i <= 9; ++i))：
- 从 1 到 9 依次选择每个数字作为顺序数字的起始数字。
内层循环 (for (int j = i + 1; j <= 9; ++j))：
- 从当前数字的下一个数字开始，构建顺序数字。
- num = num * 10 + j：通过乘以 10 和加上下一个数字来构造顺序数字。
范围检查：
- 每次生成一个新的顺序数字后，检查它是否在 [low, high] 范围内。如果是，就将其添加到结果列表中。
返回结果：
- 最后返回符合条件的排序后的数字列表。

在特定范围内生成顺序数字后，排序虽然在这个实现中是多余的（因为生成顺序数字的顺序是递增的），但在一些情况下，比如

1234,12345,2345,3456,4567,5678,6789

在这里他就会使得顺序变得奇怪起来

Java写法：

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> ans = new ArrayList<>();

        // 从1到9依次作为起始数字
        for (int i = 1; i <= 9; i++) {
            // 当前数字的初始值
            int num = i; 

            // 从当前数字的下一个数字开始构建顺序数字
            for (int j = i + 1; j <= 9; ++j) {
                num = num * 10 + j; // 生成顺序数字
                // 检查生成的数字是否在范围内
                if (num >= low && num <= high) {
                    // 符合条件则添加到结果中
                    ans.add(num); 
                }
            }
        }
        // 需要排序
        Collections.sort(ans);
        return ans;
    }
}

运行时间

时间复杂度和空间复杂度

外层循环：
- 迭代 i 从 1 到 9（共 9 次），这是常数时间 O(1)。
内层循环：
- 对于每个 i，内层循环 j 从 i + 1 到 9。这意味着：
  - 当 i = 1 时，j 迭代 8 次；
  - 当 i = 2 时，j 迭代 7 次；
  - ...
  - 当 i = 8 时，j 迭代 1 次；
  - 当 i = 9 时，j 不执行。
- 所以内层循环的总次数为 8+7+6+5+4+3+2+1=368 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 368+7+6+5+4+3+2+1=36，这也是常数时间 O(1)。
排序：
- 最后，对结果列表 ans 进行排序。最坏情况下，如果生成了最多的顺序数字（即从 10 到 123456789），则最多会有 36 个数字。
- 排序的时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn)，其中 nnn 是 ans 的大小。在最坏情况下，这个大小是 36，因此排序的复杂度实际上是 O(1)。