算法：小于n的最大数

算法题目

题目要求：给定一个数组例如nums=[2,3,4,5],n=2345,求使用nums中的数字，组成一个不大于N的最大的数字。nums中的数字可以多次使用。
备注：例如nums=[6, 8], n = 300。那么应该返回最大数字为88。

这个题目在网上有很多解答，但是大部分解答都有问题，没法完全的覆盖所有的case，因此在这里记录下我的解答。

思路与解答

思路： 贪心 + 二分
首先讲nums数组进行排序，注意下需要判断我们要寻找的最大值，如果n中的每一位数都比nums数组最小值都要小，那么我们要找寻的最大数长度为原来的n长度减一。
然后从左向右找寻n每一位在nums数组中的最大值，这里可以利用二分。在这个遍历过程中，注意后一位如果比nums数组中的最小值还要小，那么就应该这一位要找寻的最大值再减一。

/**
 * 从数组中选择元素组成小于n得最大整数
 */
public class Main{

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextLine()){
            String[] s = in.nextLine().split(" ");
            int[] nums = new int[s.length];
            for(int i = 0; i < nums.length; i++){
                nums[i] = Integer.parseInt(s[i]);
            }

            int n = Integer.parseInt(in.nextLine());
            System.out.println(new Main().getMaxLessNum(nums, n));
        }
    }

    private int getMaxLessNum(int[] nums, int n){
        Arrays.sort(nums);
        int minNum = nums[0];
        String maxNum = getMaxString(minNum, n);
        StringBuilder s = new StringBuilder();
        boolean preIndexLess = false;
        for(int i = 0; i < maxNum.length(); i++){
            int index = preIndexLess ? nums.length - 1 : search(maxNum, i, nums);
            s.append(nums[index]);
            if(nums[index] < (maxNum.charAt(i) - '0')){
                preIndexLess = true;
            }
        }

        return Integer.parseInt(s.toString());
        
    }

    // 获取要查询的最大值， 可能出现拼接不出与原来数字长度相等的数，那么就返回长度减一的最大值
    private String getMaxString(int minNum, int n){
        boolean flag = false;

        String s = String.valueOf(n);
        // 解决前一个版本出现的bug
        for(char c : s.toCharArray()){
            if((c - '0') > minNum){
                flag = true;
                break;
            }else if ((c - '0') < minNum){
                break;
            }
        }

        int maxNum = flag ? (n - 1) : (int)(Math.pow(10, s.length() - 1) - 1);
        return String.valueOf(maxNum);
    }

    /**
     * 二分查找，查找等于或者小于findNum的最右边位置
     *
     */
    private int search(String maxNum, int index, int[] nums){
        int curMax = maxNum.charAt(index) - '0';
        int minNum = nums[0];
        int findNum = curMax;
        if(index < maxNum.length() - 1){
            findNum = (maxNum.charAt(index + 1) - '0') < minNum ? curMax - 1 : curMax;
        }

        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > findNum){
                right = mid - 1;
            }else if(nums[mid] < findNum){
                left = mid + 1;
            }else{
                return mid;
            }
        }

        return right;
    }
}

时间复杂度：O(nlogn)

参考

这有篇更详细的：/m0_50043893/article/details/126543373