需求

• 给一个nums数组和target数字，需要用nums里的数字组成比target小的最大数
• 例子：nums = [2,3,6,9] targets = 2648 res = 2639

coding

package com.webapp.interview.bytedance;

import org.junit.jupiter.api.Test;

import java.util.*;

public class minNum {
    // 需要根据给定的数组里的数字组成比target小的最大数字
    // 不进行降级
    // nums = [2,3,6,9] targets = 2639 res = 2639
    // 降级
    // nums = [2,3,6,9] targets = 2648 res = 2639
    // 连续降级
    // nums = [2,3,6,9] targets = 2618 res = 2399
    // nums = [2,3,6,9] targets = 2218 res = 0999

    @Test
    public void findMin() {
        int[] nums = {2, 3, 6, 9};
        int targets = 2218;
        int res = 0;
        // 假如当前targets需要的数字都在nums里，则正好
        // 但是一旦有数字不满足，第一个不满足的位置去取当前nums里比他小的最大数，后面所有的数字都用nums里的最大数
        // 但是如果第一个不满足的位置里在nums里找不到比他小的最大数，用0替代并且，那么就需要往前进行降级，降级成功后，后面所有数取最大
        // 降级的意思是寻找比目标值小的最大数

        Arrays.sort(nums);

        // 将targets转化成数组形式
        ArrayList<Integer> targ = new ArrayList<>();
        int t = targets;
        while (t != 0) {
            targ.add(0, t % 10);
            t /= 10;
        }

        // allMax的意思是res后续都填充nums里的最大数字
        boolean allMax = false;
        for (int i = 0; i < targ.size(); i++) {
            if (!allMax) {
                int curNum = targ.get(i);

                int loc = getLoc(curNum, nums);
                if (nums[loc] == curNum)
                    res = res * 10 + curNum;
                else {
                    // 不满足条件的还需要分为是否找到比其小的最大数字
                    // 如果当前数字没有找到比其小的最大数字，则往前开始进行数字降级
                    if (loc > 0) {
                        // loc>0意味着loc-1号位置就是你需要的比当前数字小的最大数
                        // 找到了比其小的最大数
                        res = res * 10 + nums[loc - 1];
                    } else {
                        //没找到则进行数值降级
                        while (--i >= 0) {
                            curNum = res % 10;
                            res /= 10;

                            loc = getLoc(curNum, nums);
                            if (loc > 0) {
                                res = res * 10 + nums[loc - 1];
                                break;
                            }
                        }

                        // 当前降级一直降到第一个数且没有降级成功时，那么我们将第一个数变成0，让i=0，i++后就从1号位置为开始了
                        i = i >= 0 ? i : 0;
                    }
                    allMax = true;
                }
            } else res = res * 10 + nums[nums.length - 1];
        }

        System.out.println(res);
    }

    public int getLoc(int target, int[] nums) {
        int l = 0;
        int r = nums.length;

        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] < target) l = mid + 1;
            else if (nums[mid] > target) r = mid;
            else return mid;
        }

        // 如果没找到target，l会收敛到第一个不满足条件的点
        // 详细看前一篇文章
        return l;
    }
}

难点分析

• 对于target，我们从左往右寻找nums里的数字拼凑
• 本题总共需要处理四种情况
  • 第一种，target所有需要的数字全在nums里
  • nums = [2,3,6,9] targets = 2639 res = 2639
    • 这种最简单处理，直接在nums里二分查找target里需要的数字即可
  • 第二种，target从左往右存在一个不存在nums里的数字，但是nums里存在比其小的数字
  • nums = [2,3,6,9] targets = 2648 res = 2639
    • 对于这种情况，遇到第一个数字不在nums里的（2648里的4），在nums里找比它小的最大数赋值（比4小的3在nums里），然后它后面的所有数都是nums里的最大数（nums里的最大数9）
  • 第三种情况，在第二种情况的基础上，在nums里不存在比其更小的数字
  • nums = [2,3,6,9] targets = 2618 res = 2399
    • 这种情况当发现不存在这样的数时（2618中的1，nums里没有比它更小的），这个时候就需要将前面的数字进行降级（将前面一位6进行降级，去nums里找比它小的最大数3），意思就是去nums里找比其数字小的最大数，如果还是找不到则再往前
  • 第四种情况，在三的基础上连续降级一直降级到头了
  • nums = [2,3,6,9] targets = 2218 res = 0999
    • 这种情况就直接将第一位数变成0，然后后面取nums里的最大数