在小于限制的数字排列中查找最大可能的数字

Question

我想以一种结果

是最大可能的排列方式排列整数。这很容易做到，就像这样：

//how to deal with really large ints e.g.int32.MaxValue goes here 
// in this case the algorithm would need to round down to the largest possible value 
// but still needs to be less than int32.MaxValue 
//This code will just handle normal values <int32.MaxValue 
public static int Max(int number)
{
    var numberAsCharArray = number.ToString().OrderByDescending(c => c).ToArray();
    var largestNumberAsString = new string(numberAsCharArray);
    return Int32.Parse(largestNumberAsString);
}

但是，当输入具有与Int32.MaxValue相同的位数并且至少包含一个高位时，该数字将转到第一个位置，使结果> Int32.MaxValue并在转换为 int 时导致异常。

我怎样才能将结果限制为 <= Int32.MaxValue但在此限制内仍然是最大可能的排列？

注意：负数，例如 -1234567890是允许的，也是积极的;在负输入的情况下，应删除-符号：-1234567890应产生2147398650输出

Answer 1

对于较小的数字（小于或等于1000000000），您可以照常开展业务;对于大于十亿的数字;您可以尝试以下方法：

1. 尽可能遵循int.MaxValue模式（2147483647
）
2. 如果不可能，请输入您可以执行的最大数字，然后继续照常执行剩余数字的业务。

例如，给定1234567890

  1234567890 <- initial value
  2147483647 <- int.MaxValue pattern
  2147398650 <- solution
      ^
      |
      Here we can't put another 4, we put maximum available - 3
  Remaining digits [56890] we order by descending - "98650" - business as usual

实现

private static int Biggest(int value) {
  // Special MinValue case; 
  // we can't do Math.Abs() because of integer overflow
  if (value == int.MinValue)
    return 2147483486;
  string st = value.ToString().Trim('-');
  if (value <= 1000000000 && value >= -1000000000)
    return int.Parse(string.Concat(st.OrderByDescending(c => c)));
  string max = int.MaxValue.ToString();
  List<int> digits = st.Select(c => c - '0').ToList();
  StringBuilder sb = new StringBuilder(9);
  bool exact = true;
  while (digits.Any()) {
    for (int i = 0; i < max.Length; ++i) {
      int digitToFind = max[i] - '0';
      int digitActual;
      digitActual = digits
        .Where(d => !exact || d <= digitToFind)
        .OrderByDescending(d => d)
        .First();
      if (exact)
        exact = digitActual == digitToFind;
      sb.Append(digitActual);
      digits.Remove(digitActual);
    }
  }
  return int.Parse(sb.ToString());
}

测试：

// 2147398650 (for reference: int.MaxValue == 2147483647)
Console.WriteLine(Biggest(1234567890));

Answer 2

我建议这样做：

int number = 587;
int maximum = Int32.MaxValue;
var result = "";
if(number == Int32.MinValue)
{
    result = "2147483486";
}
else
{ 
    // create list of available digits removing - sign from the string
    var inputDigits = number.ToString().Replace("-", String.Empty).Select(c => Int32.Parse(new string(c, 1))).ToList();
    var limitDigits = maximum.ToString().Select(c => Int32.Parse(new string(c, 1))).ToList();
    var orderedDigits = inputDigits.OrderByDescending(c => c).ToList();
    int position = 0;
    // we only have to compare to the maximum if we have at least the same amount of digits in the input.
    bool compareValues = limitDigits.Count <= inputDigits.Count;
    // while we have not used all of the digits
    while (orderedDigits.Count > 0)
    {
        // loop over the remaining digits from high to low values
        for (int i = 0; i < orderedDigits.Count; i++)
        {
            // if it is above the digit in the maximum at the corresponding place we may only use it if input is shorter than maximum or if we have already used a lower value in a previous digit.
            if (orderedDigits[i] > limitDigits[position])
            {
                if (compareValues)
                {
                    continue;
                }
            }
            else if (orderedDigits[i] < limitDigits[position])
            {
                // remember that we have already used a lower value
                compareValues = false;
            }
            result += (orderedDigits[i].ToString());
            orderedDigits.RemoveAt(i);
            break;
        }
        position++;
    }
}
var intResult = Int32.Parse(result);

编辑：

定义inputDigits以支持负数时插入.Replace("-", String.Empty)