找到小于Y的最大可能数字。

Question

找到小于Y的最大可能数字。

3

重新排列数字X，找到小于或等于Y的最大可能数。如果不可能，则返回-1。此外，生成的输出不应该有前导零。 示例:

X = 2851
Y = 8774

答案：

说明：8521小于或等于8774，且它是可能的最大数。

这是我尝试的代码：

public String process(long X, long Y) {
 if(X > Y) return "-1";
 char[] arr = (""+X).toCharArray();
 Arrays.sort(arr);
 String s = new String(arr);
 s = new StringBuilder(s).reverse().toString();
 long x1 = Long.parseLong(s);
 if(x1 <= Y) return "" + x1;
 return "=1";
}

我的方法不正确，因为我总是检查X中给定数字的最大可能数。解决这个程序的正确方法是什么？

使用我的程序失败的另一个示例测试用例是：

示例：

X = 12222
Y = 21111

期望答案：

- learner

提示：使用TreeMap构建一个以原始数字的出现次数为值的映射表。 - SomeDude

@SomeDude，一旦创建了TreeMap，下一步是什么？例如，对于第一个例子[{1,1}, {2,1}, {5,1}, {8,1}]。 - learner

2

需要指出的一点是，你的第一个语句 if(X > Y) return "-1"; 是不正确的。考虑 x = 9231; y = 2314。X 大于 Y，但是 2139 满足所述要求。 - WJS

@AlexanderIvanchenko，我们生成的输出不应该有前导零。我会更新我的帖子以添加这个条件。 - learner

3个回答

1

@Mureinik 的答案中提出的想法可以通过减少迭代次数来增强。

我们可以创建一个大小为 10 的数组 int[]，表示数字 x 中每个数字的频率。这将消除在列表上执行删除操作的需要，该操作的成本为 O(n)，就像链接的答案中一样（相反，对应的元素将在 O(1) 中递减）。此外，频率数组的大小小于 long 数字中可能的最大位数。如果 x 和 y 被表示为 BigInteger 或数字 String，则这些优点将更加显著。

public static String process(long x, long y) {
    
    int[] target = toArray(y);
    
    int[] frequencies = getFrequencies(x);
    int[] result = new int[target.length];
    
    for (int i = 0; i < target.length; i++) {
        int nextDigit = getIndex(frequencies, target[i]); // performs at most 10 iterations
        
        if (nextDigit == -1) return "-1";
        
        result[i] = nextDigit;    // O(1)
        frequencies[nextDigit]--; // O(1)
    }
    
    return toString(result);
}

public static int getIndex(int[] freq, int digit) {
    int nextDigit = -1;
    for (int i = digit; i > 0; i--) {
        if (freq[i] > 0) {
            nextDigit = i;
            break;
        }
    }
    return nextDigit;
}

public static int[] toArray(long num) {
    
    return LongStream.iterate(num, n -> n > 0, n -> n / 10)
        .map(n -> n % 10)
        .collect(
            ArrayDeque<Long>::new,
            Deque::offerFirst,
            Collection::addAll
        )
        .stream()
        .mapToInt(Long::intValue)
        .toArray();
}

public static int[] getFrequencies(long num) {
    int[] freq = new int[10];
    long cur = num;
    while (cur != 0) {
        freq[(int) (cur % 10)]++;
        cur /= 10;
    }
    return freq;
}

public static String toString(int[] arr) {
    
    return Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining());
}

主函数()

public static void main(String[] args) {
    System.out.println(process(2851, 8774));
}

输出：

- Alexander Ivanchenko

0

你可以遍历 Y，并在每次迭代中查找 X 中剩余数字中小于或等于 Y[i] 的最大可能数字，如果找到，则将其放置在 results[i] 中（不要忘记从 X 中删除它），如果没有找到，则返回 false。

- Yosef.Schwartz

只有在给定数字的位数和最小数字的位数相等时，才能正常工作。 - Utkarsh Sahu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mureinik · Accepted Answer

我会将两个数字都分解为位数，然后针对y的每个数字，在x中查找不大于它的最大（剩余）数字。在每一步中，如果找不到这样的数字，则可以返回-1。

public static long process(long src, long max) {
    long result = 0L;
    List<Long> srcDigits = getDigits(src);
    List<Long> maxDigits = getDigits(max);
    for (Long maxDigit : maxDigits) {
        Optional<Long> digit = 
            srcDigits.stream().filter(d -> d <= maxDigit).max(Comparator.naturalOrder());
        if (digit.isEmpty()) {
            return -1L;
        }
        long srcDigit = digit.get();
        result *= 10;
        result += srcDigit;
        srcDigits.remove(srcDigit);
    }
    return result;
}

private static List<Long> getDigits(long num) {
    List<Long> digits = new LinkedList<>();
    while (num > 0) {
        digits.add(0, num % 10);
        num /= 10;
    }
    return digits;
}