0

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

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

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

4

3 回答 3

2

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

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

编辑：使用上述算法的最佳解决方案 - 使用范围最小查询来计算每个连续数字位置可能的最大值。理论上，这可以在每次查询的恒定时间和使用线性预计算的线性额外内存中完成，但该算法非常复杂且难以实现，它只会为您提供非常大的 n 值的改进。我个人建议使用会导致 O(n*log(n)) 时间复杂度的分段树方法。

于 2012-07-02T13:14:20.963 回答
0

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

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;
}
于 2012-07-02T13:24:11.110 回答
0

如果您可以访问代码，请将数字存储为带有分隔符（空格、逗号等）的字符串，然后使用字符串分隔符函数将每个数字（字符串字符）放入它自己的数组位置。解析字符串数组并制作一个整数数组。然后对数组进行快速排序。完成后，取前 X 个整数，这就是你的数字。

于 2012-07-02T13:07:56.800 回答