可由给定数字构成的最大数目。

Question

给定一个整数，找到可以由这些数字形成的最大数目。输入: 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 1 2 1 1 1 0)的数字计数后的哈希表(0 0 0 1 1 2 1 1 1 0)按反序$\rightarrow$ 8765543的时间复杂度打印哈希表的索引:如果我错了，O(n)更正我。

Answer 1

以下贪婪的代码在O(n)时间内这样做。其中n是数字中的数字数。

int num = 8756404;
int[] times = new int[10];
while(true){
    if(num==0){
        break;
    }
    int val = num%10;
    times[val]++;
    num /= 10;
}
for(int i=9; i>=0; i--){
    for(int j=0; j<times[i]; j++){
        System.out.print(i);
    }
}

它通过计算输入数字中每个数字的出现数来工作。然后打印每一个数字的次数，它是在输入数字的反向顺序，即。从9开始到0。

Answer 2

RunTime：00:00:00.01

public int Assignment(int number) 
{
    // Consider that int.MaxValue equals to 2147483647
    var siblingString = String.Join("", number.ToString().ToCharArray().OrderByDescending(n => n));
    int sibling = -1;
    if (!int.TryParse(siblingString, out sibling) || sibling > 100000000)
    {
        return -1;
    }
    return sibling;
}

使用以下代码测试性能：

static void Main()
{
    Stopwatch stopWatch = new Stopwatch();

    stopWatch.Start();
    var result = AssignmentOne(2147483646);
    stopWatch.Stop();

    TimeSpan ts = stopWatch.Elapsed;
    string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);
    Console.WriteLine("RunTime " + elapsedTime);
}