可以由给定的数字组成的最大数字

问题描述 投票:1回答:2

给出一个整数,找到可以由数字组成的最大数字。输入:8754365输出:8765543

我以$ O(n logn)$告诉解决方案。他要求我进一步优化。

我们可以使用哈希表进一步优化,$ \ rightarrow $ O(n)

算法:1.取一个大小为10(0到9)的哈希表。2.存储从0到9的每个数字的计数。3.相对于反向计数(从9到0)打印哈希表的索引。

示例:

哈希计数后的位数为8754365 $ \ rightarrow $(0 0 0 1 1 2 2 1 1 1 0)以相反的顺序打印哈希表相对于其计数的索引$ \ rightarrow $ 8765543时间复杂度:O(n)如果我错了,请纠正我。

给出一个整数,找到可以由数字组成的最大数字。输入:8754365输出:8765543我在$ O(n logn)$中告诉解决方案。他要求我进一步优化。我们可以使用哈希表...

algorithm hash
2个回答
2
投票

以下贪婪的code在O(n)时间内完成此操作。其中n是数字中的位数。


0
投票

RunTime

© www.soinside.com 2019 - 2024. All rights reserved.