经典面试题-小于N的最大数

给定一个数字字符串S和一个数组nums，数组中的元素都在0~9之间，问从数组中选择元素组成的数字，小于N的最大值是多少？

例如：S = "24378"，nums:{2,3,9}，组成的最大值为23999。

先给出代码：

public class Code01 {
 
    public static void main(String[] args) {
        int[] nums = new int[]{2,3,9};
        int N = 24399;
        System.out.println(getMaxBelowN(nums,N));
        System.out.println(getMaxLessNum(nums,N));
 
    }
    public static String getMaxLessNum(int[] nums,int N){
        Arrays.sort(nums);
        String maxBelow = getMaxBelowN(nums,N);
        StringBuilder sb = new StringBuilder();
        boolean flag = false;
        for(int i = 0; i < maxBelow.length(); i++){
            /*
            每位都找小于等于该位最大的数，如果maxBelow这个位置的数大于等于nums的最大值，就用最大值
            否则去数组找最接近的
            如果当前从数组中找的数字小于maxBelow对应这位的数字，此后选择的数字都可以是数组中的最大值
            例如2513和{2,4,6,8}
            选到第二位4之后，4比5小，此后就可以都选择8，组成2488
             */
            char c = maxBelow.charAt(i);
            if(flag){
                sb.append(nums[nums.length - 1]);
            }else{
                //拿到应该选择数字的下标
                int index = getIndex(nums,maxBelow,i);
                sb.append(nums[index]);
                //如果选择的数字比当前这位小，此后就都选最大值
                if(nums[index] < c - '0') flag = true;
            }
        }
        return sb.toString();
    }
 
    /*
    能否拼出N长度的数？还是只能拼出N长度-1的数
    怎么判断能拼出来？
    判断str的第一位与nums[0]的大小关系
     */
    public static String getMaxBelowN(int[] nums,int N){
        String str = String.valueOf(N);
        int min = nums[0];
        boolean flag = check(str,min);
        int num = flag ? (N - 1) : (int)Math.pow(10,str.length() - 1) - 1;
        return String.valueOf(num);
    }
 
    //检查能否用数组拼出相同长度的数字字符串
    public static boolean check(String str,int minValue){
        if(str.equals("")) return true;
        char c = str.charAt(0);
        if(c - '0' > minValue){
            return true;
        }else if(c - '0' < minValue){
            return false;
        }else{
            return check(str.substring(1),minValue);
        }
    }
 
    public static int getIndex(int[] nums,String maxBelow,int index){
        int curNum = maxBelow.charAt(index) - '0';
        if(index < maxBelow.length() - 1){
            int nextNum = maxBelow.charAt(index+1) - '0';
            //下一位不能小于等于nums[0]，否则就要选小于curNum的数
            if(nextNum <= nums[0]){
                curNum -= 1;
            }
        }
 
        //curNum处理完成后，找到小于等于curNum的数
        int left = 0,right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == curNum){
                left = mid + 1;
            }else if(nums[mid] < curNum){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return right;
    }
}

看一下整体的思路流程：

1、首先拿到原始字符串S和数组nums，首先要想能拼出和S长度一样的字符串吗？

怎么判断？

我们拿到数组中最小的数字（在这之前将数组从小到大排序），得到minValue，与S的第一位相比。

        1）如果minValue大于S的第一位，说明无论从数组中选择什么数字，得到的结果都会比S大，所以明显不能拼出相同长度的字符串了，只能将长度减1。

        2）如果minValue小于S的第一位，OK，现在能拼出相同长度的字符串了

        3）如果二者相同，那么能得到相同长度的字符串吗？递归看下一位即可，道理同1）2）

//检查能否用数组拼出相同长度的数字字符串
public static boolean check(String str,int minValue){
    if(str.equals("")) return true;
    char c = str.charAt(0);
    if(c - '0' > minValue){
        return true;
    }else if(c - '0' < minValue){
        return false;
    }else{
        return check(str.substring(1),minValue);
    }
}

2、获取到结果字符串的长度之后，怎么处理？

例如原始字符串S = "2413"，如果能获取相同长度的字符串，我们理论上能得到的最大值就是2412；

但如果数组是[4,6,8]，很明显我们不能获得4位长度的字符串，此时能得到的理论最大数maxBelow是多少呢？

是999

于是，通过如下代码，我们获取到从数组中得到的理论最大值maxBelow。

public static String getMaxBelowN(int[] nums,int N){
    String str = String.valueOf(N);
    int min = nums[0];
    boolean flag = check(str,min);
    int num = flag ? (N - 1) : (int)Math.pow(10,str.length() - 1) - 1;
    return String.valueOf(num);
}

3、获取到结果字符串的长度之后，就要开始拼接字符串了。

怎么拼接？

每次都去找数组中小于等于该位置上最大的数拼接

但请注意，如果从数组中选择的数字小于maxBelow当前位置的数字的话，此后都要选择数组中的最大值来拼接

例如2413和{2,3,6,8}：拼接到23之后，因为3小于4，此后都可以选择8来拼接后面的部分，得到结果2388

public static String getMaxLessNum(int[] nums,int N){
    Arrays.sort(nums);
    String maxBelow = getMaxBelowN(nums,N);
    StringBuilder sb = new StringBuilder();
    boolean flag = false;
    for(int i = 0; i < maxBelow.length(); i++){
        /*
        每位都找小于等于该位最大的数，如果maxBelow这个位置的数大于等于nums的最大值，就用最大值
        否则去数组找最接近的
        如果当前从数组中找的数字小于maxBelow对应这位的数字，此后选择的数字都可以是数组中的最大值
        例如2513和{2,4,6,8}
        选到第二位4之后，4比5小，此后就可以都选择8，组成2488
        */
        char c = maxBelow.charAt(i);
        if(flag){
            sb.append(nums[nums.length - 1]);
        }else{
            //拿到应该选择数字的下标
            int index = getIndex(nums,maxBelow,i);
            sb.append(nums[index]);
            //如果选择的数字比当前这位小，此后就都选最大值
            if(nums[index] < c - '0') flag = true;
        }
    }
    return sb.toString();
}

4、从3里的代码看，我们需要获取小于等于target的数字下标

怎么获得下标？

二分法，类似于找到小于等于target的右边界。

注意，选择数字还要受到maxBelow下一位数字的影响

例如：maxBelow为2411，nums为{2,4,6,8}

按照【说明3】里面的逻辑，第二位数字应该选4，但如果选了4，后面再拼接就一定会大于maxBelow了。

因此，选择数字要受到下一位的影响。我们就要对当前位置的数字进行处理。

public static int getIndex(int[] nums,String maxBelow,int index){
    int curNum = maxBelow.charAt(index) - '0';
    if(index < maxBelow.length() - 1){
        int nextNum = maxBelow.charAt(index+1) - '0';
        //下一位不能小于等于nums[0]，否则就要选小于curNum的数
        if(nextNum <= nums[0]){
            curNum -= 1;
        }
     }
 
    //curNum处理完成后，找到小于等于curNum的数
    int left = 0,right = nums.length - 1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == curNum){
           left = mid + 1;
        }else if(nums[mid] < curNum){
           left = mid + 1;
        }else{
           right = mid - 1;
        }
     }
     return right;
}

此处二分法返回的下标问题：

1）如果target在数组的左右范围中，自然能正确返回结果；

2）如果target大于数组中最大的数，那么返回right是正确的；

3）如果target小于数组中最小的数，基于题目的情景，不会存在这样的情况。

基于getIndex()对当前位置数字的处理，如果下一位数字小于minValue，当前位就会选择更小的数字，下一位就可以选择最大值了。

例如2413和{2,4,6,8}。在查找1之前，第二位已经用2代替了，第三位就可以直接使用8。

如果有BUG欢迎各位指正。