所以，最近我在检查一个编码挑战这个问题很有趣，所以只想知道是否有更好的方法来处理时间和空间的复杂性。
问题：给定一个数字x，其中x将是大于0的正数。用相同的位数找到最近的最小数。如果它存在，所以返回最小的数字，否则打印“最近的最小数目不存在”。我所说的相同位数是指，如果数字是12345，那么用这些位数（在本例中，位数是5）就找不到最近的较小的数字。虽然你可以说它可以是1234，但它的位数不同。当你找到最接近的最小数字时，你需要利用所有的数字
下面是几个例子
号码：8563
产量：8536
7385号
输出7358
号码：3857
产量：3785
号码：123
输出：最小的最小数不存在
number = gets.to_i
flag = 1
numbers_array = number.digits.permutation(Math.log10(number).to_i + 1).sort
numbers_array.each_with_index do |e, index|
if e.join.to_i == number
print numbers_array[index - 1]
flag = 0
break
end
end
if flag == 1
puts "Nearest Smallest Number not exist"
end
注：以上的解决方案需要更多的时间，当数字很大时
最佳答案
这个想法类似于生成数组的下一个置换。
假设我们有一个排列
a1, a2, a3 ... an
前面的排列是什么？
观察：
第一个置换（最小的置换）将具有以下特性：
a1 <= a2 <= a3 ... <= an
最后一个排列有这个性质：
a1 >= a2 >= a3 ... >= an.
从这个观察中，我们可以很容易地从一个给定的排列中来回移动。
让我们从最后一个元素迭代到第一个元素，如果我们可以找到一个
k位置：ak , ak + 1, and ak > ak + 1
让我们从
ak + 1 ... an中找出最大的数字，称之为满足ax的ax < ak，并用ax替换ak，现在我们得到的是a1, a2, ... ax, [...]
对于[…]，我们应该做的是按降序对它们进行排序。沃拉，我们找到了问题的答案。
例子：
1, 2, 4, 3 => k = 3, x = 4 -> Ans = 1, 2, 3, 4
1, 2, 5, 5, 3, 4 => k = 4, x = 6 -> Ans = 1, 2, 5, 4, 5, 3
Java代码：
public void prevPermutation(int[]data){
for(int i = data.length - 2; i >= 0; i--){
if(data[i] > data[i + 1]){
int index = i + 1;
for(int j = i + 2; j < data.length; j++){
if (data[j] > data[index] && data[j] < data[i]){
index = j;
}
}
int tmp = data[i];
data[i] = data[index];
data[index] = tmp;
sortDescending(data, i + 1, data.length);
break;
}
}
}
public void sortDescending(int[]data, int from, int to){
int[]copy = Arrays.copyOfRange(data, from, to);
Arrays.sort(copy);
for(int i = from; i < to; i++){
data[i] = copy[to - i - 1];
}
}
时间复杂度：
O (n log n)以n为数字个数。现场演示：https://ideone.com/ZLaSa0
稍好的版本：
O (n)时间复杂度https://ideone.com/RvmymX
关于ruby - 编码挑战，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58444393/