寻找相同数字组成的下一个更大数 | Baeldung中文版

1. 引言

本文将探讨如何在Java中寻找由相同数字组成的下一个更大数。这个问题可以通过排列组合、排序和双指针技术解决，每种方法都有其适用场景。

2. 问题定义

给定一个正整数，要求找出使用完全相同数字组成的下一个更大数。例如：

输入 123，输出应为 132
输入 654 或 444，返回 -1（表示不存在更大数）

⚠️ 关键点：必须严格使用原数字的所有数字，不能添加或删除。

3. 排列组合法

3.1 实现思路

通过生成所有数字排列组合，找出比原数大的最小值。使用TreeSet自动去重和排序：

void findPermutations(int num, int index, StringBuilder sb, Set<Integer> hs) {
    if (index == String.valueOf(num).length()) {
        hs.add(Integer.parseInt(sb.toString()));
        return;
    }
    //...
}

核心步骤：

递归终止条件：当索引达到数字长度时，将当前排列加入集合
生成排列：通过交换字符位置递归生成所有排列
状态恢复：递归返回后交换回字符，确保后续排列正确

for (int i = index; i < String.valueOf(num).length(); i++) {
    char temp = sb.charAt(index);
    sb.setCharAt(index, sb.charAt(i));
    sb.setCharAt(i, temp);
    findPermutations(num, index + 1, sb, hs);
    sb.setCharAt(index, temp); // 恢复状态
    sb.setCharAt(i, sb.charAt(index));
}

主方法实现：

int findNextHighestNumberUsingPermutation(int num) {
    Set<Integer> hs = new TreeSet();
    StringBuilder sb = new StringBuilder(String.valueOf(num));
    findPermutations(num, 0, sb, hs);
    for (int n : hs) {
        if (n > num) {
            return n;
        }
    }
    return -1;
}

3.2 测试验证

assertEquals(536497, findNextHighestNumberUsingPermutation(536479));
assertEquals(-1, findNextHighestNumberUsingPermutation(987654));

3.3 复杂度分析

时间复杂度：O(n!)（n为数字位数）
- 生成所有排列组合是主要开销
空间复杂度：O(n!)
- 最坏情况下TreeSet存储所有排列

❌ 缺点：数字位数增加时，阶乘级增长会迅速导致性能崩溃

4. 排序法

4.1 实现思路

通过数学规律和排序操作高效求解：

int findNextHighestNumberUsingSorting(int num) {
    String numStr = String.valueOf(num);
    char[] numChars = numStr.toCharArray();
    int pivotIndex;
    // ...
}

关键步骤：

寻找转折点：从右向左找到第一个小于右边数字的位

for (pivotIndex = numChars.length - 1; pivotIndex > 0; pivotIndex--) {
 if (numChars[pivotIndex] > numChars[pivotIndex - 1]) {
     break;
 }
}

检查无解情况：

if (pivotIndex == 0) {
 return -1; // 数字已降序排列
}

找到最小大于pivot的数字：

int pivot = numChars[pivotIndex - 1];
int minIndex = pivotIndex;
for (int j = pivotIndex + 1; j < numChars.length; j++) {
 if (numChars[j] > pivot && numChars[j] < numChars[minIndex]) {
     minIndex = j;
 }
}

交换并排序：

swap(numChars, pivotIndex - 1, minIndex);
Arrays.sort(numChars, pivotIndex, numChars.length);
return Integer.parseInt(new String(numChars));

4.2 测试验证

assertEquals(536497, findNextHighestNumberUsingSorting(536479));
assertEquals(-1, findNextHighestNumberUsingSorting(987654));

执行流程示例（输入536479）：

找到pivot=7（索引4）
在右侧找到最小大于7的数字9（索引5）
交换7和9 → 536497
对索引5后的部分排序（无需操作）

4.3 复杂度分析

时间复杂度：O(n log n)
- 主要开销来自排序操作
空间复杂度：O(n)
- 存储字符数组

✅ 优点：比排列组合法显著高效

5. 双指针法

5.1 实现思路

优化排序法，用双指针和反转操作替代排序：

int findNextHighestNumberUsingTwoPointer (int num) {
    String numStr = String.valueOf(num);
    char[] numChars = numStr.toCharArray();
    int pivotIndex = numChars.length - 2;
    int minIndex = numChars.length - 1;
    // ...
}

辅助方法：

void swap(char[] numChars, int i, int j) {
    char temp = numChars[i];
    numChars[i] = numChars[j];
    numChars[j] = temp;
}

void reverse(char[] numChars, int i, int j) {
    while (i < j) {
        swap(numChars, i, j);
        i++;
        j--;
    }
}

核心步骤：

寻找转折点：

while (pivotIndex >= 0 && numChars[pivotIndex] >= numChars[pivotIndex+1]) {
 pivotIndex--;
}

检查无解情况：
```
if (pivotIndex == -1) {
 return -1;
}
```

找到交换位：

while (numChars[minIndex] <= numChars[pivotIndex]) {
 minIndex--;
}

交换并反转：

swap(numChars, pivotIndex, minIndex);
reverse(numChars, pivotIndex+1, numChars.length-1);
return Integer.parseInt(new String(numChars));

5.2 测试验证

assertEquals(536497, findNextHighestNumberUsingTwoPointer(536479));
assertEquals(-1, findNextHighestNumberUsingTwoPointer(987654));

执行流程示例（输入536479）：

pivotIndex停在4（数字7）
minIndex停在5（数字9）
交换7和9 → 536497
反转索引5后的部分（单元素无需操作）

5.3 复杂度分析

时间复杂度：O(n)
- 最多两次线性扫描
空间复杂度：O(1)
- 仅使用常数级额外空间

✅ 优势：最优时间复杂度，适合大位数数字

6. 方法对比总结

方法	时间复杂度	空间复杂度	适用场景
排列组合法	O(n!)	O(n!)	数字位数极少（n≤5）
排序法	O(n log n)	O(n)	代码简洁性优先
双指针法	O(n)	O(1)	大位数数字（生产环境首选）

⚠️ 踩坑提醒：

排列组合法在n>10时基本不可用
排序法在边界条件处理容易出错
双指针法需要理解反转替代排序的原理

7. 结论

本文通过三种方法解决了相同数字组成下一个更大数的问题：

排列组合法：暴力解法，仅适用于极小规模
排序法：平衡实现复杂度和性能
双指针法：最优解，时间空间复杂度均最优

推荐选择：生产环境优先使用双指针法，其线性时间复杂度和常数空间复杂度能高效处理大位数数字。对于简单场景或教学演示，排序法也是不错的选择。

本文示例代码已上传至GitHub仓库，欢迎参考实践。

Persistence

REST

Security