如何獲得由整數的一些數字組成的最大數字

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方法。