如何获得由整数的一些数字组成的最大数字

Question

我有一个数字。这个号码有很多数字。我想写一个函数，返回由该数字的一些数字组成的最大数字。在获得最大的数字时，数字的顺序不应改变。

int myFunction(int n, int cat){ 
    ... 
    return max; 
} 

如果n = 38462637和cat = 3的函数必须返回86637，即如果cat = 3功能可望恢复5位数字，如8 - 3 = 5。原始号码有5位数字的多种变体，但最大可能的数字是86637。在这种情况下，最重要的要求是数字不应该改变它们的位置。

Answer 1

这可能是有点过于复杂，但它似乎工作：

public static int myFunction(int n, int cat) { 
    String numString = String.valueOf(n); 
    int finalLength = numString.length() - cat; 
    int[] positions = new int[finalLength]; 
    StringBuilder answer = new StringBuilder(); 
    for (int i = 0; i < finalLength; i++) { 
     for (int j = (i == 0 ? i : positions[i - 1] + 1); j <= numString.length() - finalLength + i; j++) { 
      if (positions[i] == 0 || numString.charAt(j) > numString.charAt(positions[i])) { 
       positions[i] = j; 
      } 
     } 
     answer.append(numString.charAt(positions[i])); 
    } 
    return Integer.parseInt(answer.toString()); 
} 

[编辑]：没有所有的String废话一个清洁的版本：

public static int myFunction(int n, int cat) { 
    List<Integer> digits = new ArrayList<Integer>(); 
    int number = n; 
    while (number > 0) { 
     digits.add(number % 10); 
     number /= 10; 
    } 
    int finalLength = digits.size() - cat; 
    int lastIndex = digits.size(); 
    int answer = 0; 
    for (int i = 0; i < finalLength; i++) { 
     int highestDigit = -1; 
     for (int j = lastIndex - 1; j >= finalLength - i - 1; j--) { 
      if (digits.get(j) > highestDigit) { 
       highestDigit = digits.get(j); 
       lastIndex = j; 
      } 
     } 
     answer = answer * 10 + highestDigit; 
    } 
    return answer; 
} 

Answer 2

如果您有权访问该代码，请将该数字作为字符串存储在分隔符（空格，逗号等）中，然后使用字符串分隔符函数将每个数字（字符串字符）放入其自己的数组位置。解析字符串数组并创建一个整数数组。然后在数组上进行快速排序。完成后，取第一个X的整数，这就是你的号码。

Answer 3

贪婪 - 选择答案中最左边的最大数字（如果有几个位置出现此数字，请选择其最左边的出现位置）。如果数字不是0，那么数字可能是最左边的，我们右边至少有n-cat-1个数字。

之后，使用相同的算法来创建该数字的位置右侧的最大数字，该数字的位置正好为n - cat - 1数字。继续迭代，直到你有你的号码组成。请注意，您在第一次迭代后选择的数字可能为零（因为它们将不再位于结果数字的最左边）

编辑：使用上述算法的最佳解决方案 - 使用range minimum query来计算是可能的每个连续的数字位置。理论上，这可以在每个查询的恒定时间内完成，并且使用线性预计算可以实现线性额外内存，但是该算法非常复杂且难以实现，因此它只会为真正的大值n提供改进。我个人建议使用会导致O（n * log（n））时间复杂度的segment tree方法。