问题陈述 - 找到有效的算法和运行时间更少的代码

Question

我有这个问题陈述：

如果两个非负整数可以通过重新排列它们的十进制表示的数字从彼此获得，则它们被称为兄弟。例如，123 和 213 是兄弟姐妹。 535和355也是兄妹

由一个非负整数N及其所有兄弟组成的集合称为N的族。例如553的族包含三个数：355, 535 and 553.

写一个函数：

class Solution { public int solution(int N); }

即，给定一个非负整数 N，return 是 N 族中最大的数。如果结果超过 [=16，则函数应该 return −1 =].

例如，给定 N = 213 函数应该 return 321。给定 N = 553 函数应该 return 553.

为以下假设写一个efficient algorithm：

N 是 [0..2,147,483,647].

范围内的整数

代码片段#1：

public static int solution(int N) 
{
    if (N < 0) 
        throw new ArgumentException("N should be non-negative number");

    if (N == 0) 
        return 0;
    
    List<int> numbers = new List<int>();

    do {
        numbers.Add(N % 10);
        N /= 10;
    } while(N > 0);
    
    numbers.Sort();
    numbers.Reverse();
    
    int result = numbers[0];

    for (int i = 1; i < numbers.Count; i++) 
    {
        result = result * 10 + numbers[i];

        if (result > 100000000)
            return -1;
    }       

    return result;
}

代码片段#2：

public static int solution(int N)
{
    if (N < 0)
        throw new ArgumentException("N should be non-negative number");

    if (N < 10)
        return N;

    // count the frequency of each digit
    int[] digitFreqs = new int[10];
    do
    {
        digitFreqs[N % 10]++;
        N /= 10;
    } while (N > 0);

    // loop through the digit frequencies backwards to build the final answer
    int sol = 0;
    for (int i = digitFreqs.Length; i-- > 0;)
    {
        int digit = i;
        int frequency = digitFreqs[i];
        for (int j = 0; j < frequency; j++)
        {
            sol = sol * 10 + digit;

            if (sol > 100000000)
                return -1;
        }
    }
    return sol;
}

这些代码片段运行符合预期，输出正确。在这两者中，想知道哪一个在效率和运行时间方面最好。或者有任何使用其他算法进行改进的建议吗？

请帮忙！ TIA

Answer 1

不用排序，数一下十位数就够了。要获得数字，您从整数到字符串的转换似乎很好，但您可以通过注意 N % 10 是 N - 10 * (N / 10).

来节省模数

要获得最大的数字，请使用重复计数通过递减值连接数字。

例如213 -> 0000001110 -> 312; 553 -> 0000201000 -> 553.

对于计算最终整数的偏执方法，您可以预先填写由所有数字重复任意次数组成的数字表，以及 10 的倍数以进行移位。

例如321= (3.10 + 2).10 + 1, 553 = 55.10 + 3.

表：

-
9
99
999
9999
...
-
8
88
888
8888
...

Answer 2

您的两个解决方案都遵循相同的基本步骤：

将数字分解成数字
将数字降序排列
将数字转换回整数

运行时可能存在细微差异（例如，由于字符串转换），但这些差异应该可以忽略不计。查看哪种实现速度更快的唯一方法是使用数千个典型输入对它们进行基准测试。

为了澄清，他们说您可以通过根据输入中数字的频率构建最终答案来避免对数字进行排序。

 public static int solution(int N)
 {
    if (N < 0)
        throw new ArgumentException("N should be non-negative number");

    if (N < 10)
        return N;

    // count the frequency of each digit
    int[] digitFreqs = new int[10];
    do
    {
        digitFreqs[N % 10]++;
        N /= 10;
    } while (N > 0);

    // loop through the digit frequencies backwards to build the final answer
    int sol = 0;
    for (int i = digitFreqs.Length; i-- > 0;)
    {
        int digit = i;
        int frequency = digitFreqs[i];
        for (int j = 0; j < frequency; j++)
        {
            sol = sol * 10 + digit;

            if (sol > 100000000)
                return -1;
        }
    }
    return sol;
}

对于如此小的输入，这可能不会产生太大影响，但这是一个不错的建议，可能值得进行基准测试。

Answer 3

测量后，我要修正我的猜测。计数排序比正常的 Array.Sort().

快一点

这是我的尝试：

public int Fast(int N) 
{
    Span<short> buckets = stackalloc short[10];
    while (N > 0)
    {
        var d = N % 10;
        buckets[d]++;
        N /= 10;
    }

    var result = 0;
    for (int i = 9; i >= 0; i--)
    {
        for (int j = 0; j < buckets[i]; j++)
        {
            result = 10 * result + i;
        }
    }

    return result > 100000000 ? -1 : result;
}

在我的电脑上，这比您的第一个解决方案（名为“Verbose”）快大约 3 倍：

Method	Number	Mean	Error	StdDev
Verbose	5587	46.49 ns	0.933 ns	1.111 ns
Terse	5587	245.19 ns	4.932 ns	8.507 ns
Fast	5587	13.98 ns	0.304 ns	0.285 ns
Verbose	2103578	84.22 ns	1.662 ns	1.848 ns
Terse	2103578	375.10 ns	7.383 ns	11.275 ns
Fast	2103578	21.55 ns	0.456 ns	0.625 ns

问题陈述 - 找到有效的算法和运行时间更少的代码

Problem Statement - Finding the efficient algorithm and the code which gives less runtime

c#

algorithm

data-structures