如何在O(1)时空复杂度中找到排列中最大的数？

Question

我有非负整数N,我需要在N的排列中找到最大的数字.

例如,给定N = 213函数应该返回321.

如何在O(1)时间和空间复杂性方面做到这一点？

N是[0 ... 2,147,483,647]范围内的整数

如果结果超出100 000 000我们可以返回-1

Answer 1

你不能这样做O(1),你必须从最高到最低的数字列表排序,所以你可以做的最快是基于排序算法的复杂性.您可以在此处查看各种排序算法的时间和空间复杂性

Answer 2

计算每个数字的次数,然后创建一个首先具有最高位数的数字,然后创建下一个较小的数字等.

例: N=234543

2: 1 time
3: 2 times
4: 2 times
5: 1 time

现在创建一个5曾经作为第一个数字,然后4两次,3两次和2一次的数字 - 因此你得到了544332.

这是在O(Number of digits)但不限于的大小int.它可以是任何数字(以字符串或类似的形式表示).

这是一种计算排序的情况,其中不同项目的数量是10.