0

I want to ask how I can reorder the digits in an Int32 so they result in the biggest possible number. Here is an example which visualizes what I am trying to do:

2927466  -> 9766422
12492771 -> 97742211

I want to perform the ordering of the digits without using the System.Linq namespace and without converting the integer into a string value. This is what I got so far:

public static int ReorderInt32Digits(int v)
    {
        int n = Math.Abs(v);
        int l = ((int)Math.Log10(n > 0 ? n : 1)) + 1;
        int[] d = new int[l];
        for (int i = 0; i < l; i++)
        {
            d[(l - i) - 1] = n % 10;
            n /= 10;
        }
        if (v < 0)
            d[0] *= -1;
        Array.Sort(d);
        Array.Reverse(d);
        int h = 0;

        for (int i = 0; i < d.Length; i++)
        {
            int index = d.Length - i - 1;
            h += ((int)Math.Pow(10, index)) * d[i];
        }
        return h;
    }

This algorithm works flawlessly but I think it is not very efficient. I would like to know if there is a way to do the same thing more efficiently and how I could improve my algorithm.

4

5 回答 5

9

您可以使用以下代码：

var digit = 2927466;
String.Join("", digit.ToString().ToCharArray().OrderBy(x => x));

或者

var res = String.Join("", digit.ToString().ToCharArray().OrderByDescending(x => x) );
于 2015-05-27T00:40:40.637 回答
3

并不是说我的回答可能会或可能不会更“有效”，但是当我阅读您的代码时，您会计算出您的号码中有多少位数字，这样您就可以确定阵列的大小，然后您计算出如何转动阵列回到一个排序的整数。

在我看来，您可能想编写自己的代码来完成排序部分而不使用内置功能，这就是我的示例所做的。另外，我添加了按升序或降序排序的功能，这也很容易添加到您的代码中。

更新

原始算法对数字进行排序，现在它对数字进行排序，以便最终结果是最大或最小取决于传入的第二个参数。但是，在处理负数时，第二个参数被视为相反。

using System;

public class Program
{
    public static void Main()
    {
        int number1 = 2927466;
        int number2 = 12492771;
        int number3 = -39284925;

        Console.WriteLine(OrderDigits(number1, false));
        Console.WriteLine(OrderDigits(number2, true));
        Console.WriteLine(OrderDigits(number3, false));
    }

    private static int OrderDigits(int number, bool asc)
    {   
        // Extract each digit into an array
        int[] digits = new int[(int)Math.Floor(Math.Log10(Math.Abs(number)) + 1)];
        for (int i = 0; i < digits.Length; i++)
        {
            digits[i] = number % 10;
            number /= 10;
        }

        // Order the digits
        for (int i = 0; i < digits.Length; i++)
        {
            for (int j = i + 1; j < digits.Length; j++)
            {               
                if ((!asc && digits[j] > digits[i]) ||
                    (asc && digits[j] < digits[i]))
                {
                    int temp = digits[i];
                    digits[i] = digits[j];
                    digits[j] = temp;
                }
            }
        }

        // Turn the array of digits back into an integer
        int result = 0;     
        for (int i = digits.Length - 1; i >= 0; i--)
        {
            result += digits[i] * (int)Math.Pow(10, digits.Length - 1 - i);
        }

        return result;
    }
}

结果：

9766422
11224779
-22345899

在此处查看工作示例... https://dotnetfiddle.net/RWA4XV

于 2015-05-27T02:23:08.960 回答
1 
public static int ReorderInt32Digits(int v)
{
    var nums = Math.Abs(v).ToString().ToCharArray();
    Array.Sort(nums);
    bool neg = (v < 0);
    if(!neg)
    {
        Array.Reverse(nums);    
    }
    return int.Parse(new string(nums)) * (neg ? -1 : 1);
}
于 2015-05-27T01:03:14.710 回答
1

下面的代码片段从变量 v 中提取数字。您可以修改它以将数字存储在数组中并排序/反转。

int v = 2345;

while (v > 0) {
   int digit = v % 10;
   v = v / 10;
   Console.WriteLine(digit);
}

您可以使用类似的逻辑从（排序的）数字重构数字：乘以 10 并添加下一个数字。

于 2015-05-27T01:03:28.283 回答
1

我发布第二个答案是因为我认为我得到了最有效的算法（感谢 Atul 的帮助）:)

void Main()
{
    Console.WriteLine (ReorderInt32Digits2(2927466));
    Console.WriteLine (ReorderInt32Digits2(12492771));      
    Console.WriteLine (ReorderInt32Digits2(-1024));
}

public static int ReorderInt32Digits2(int v)
{
    bool neg = (v < 0);
    int mult = neg ? -1 : 1;
    int result = 0;
    var counts = GetDigitCounts(v);
    for (int i = 0; i < 10; i++)
    {
        int idx = neg ? 9 - i : i;
        for (int j = 0; j < counts[idx]; j++)
        {
            result += idx * mult;
            mult *= 10;         
        }
    }
    return result;
}

// From Atul Sikaria's answer
public static int[] GetDigitCounts(int n)
{
    int v = Math.Abs(n);
    var result = new int[10];
    while (v > 0) {
        int digit = v % 10;
        v = v / 10;
        result[digit]++;
    }
    return result;
}
于 2015-05-27T20:51:09.253 回答