求小于目标值的最大值

[Twlig]

给定一个目标值29999，以及数组，使用数组中的数字组合成小于该目标值的最大值。 思路：

• 对数组arr从大到小排序，把目标值target转为数字数组tarArr。
• 声明一个数组indexArr用于存放小于tarArr[i]的arr索引值，不存在则-1。一个resArr数组用来存放结果值，初始化为-1
• 从0开始遍历（即从最高位开始考虑）tarArr数组，如果arr存在等于tarArr[i]的数，则赋值给resArr，并记录indexArr
• 如果resArr[i] === -1则调用set函数。找到比第i位小的数，如果找不到更小的，则往前推，把前一位设置成更小的。其他位都设置成arr中最大的。
• 注意如果第0位不存在比它更小的，则需要删除。

  
  let arr = [1, 5, 8, 4]
  let target = 29999
  function arrToNumber(arr) {
  return parseInt(arr.join(''))
  }

function set(resArr, index, indexArr, arr) { let temp while (index >= 0) { temp = indexArr[index] if(index === 0 && temp === -1) { resArr.splice(0, 1) resArr.fill(arr[0]) break } if(temp !== -1) { resArr[index] = arr[temp] resArr.fill(arr[0], index + 1) break } index-- } }

function getMin(arr, target) { let tarArr = (target + '').split("").map(value => parseInt(value)) arr.sort((a, b) => b - a) let m = tarArr.length let n = arr.length let indexArr = new Array(m).fill(-1) let resArr = new Array(m).fill(-1) for(let i = 0; i < m; i++) { for(let j = 0; j < n; j++) { if(arr[j] === tarArr[i]) { resArr[i] = arr[j] } if(arr[j] < tarArr[i] && indexArr[i] === -1) { indexArr[i] = j break } } if(resArr[i] === -1) { set(resArr, i, indexArr, arr) break } } let res = arrToNumber(resArr) let isSame = res === target if(isSame) { if(indexArr[m - 1] !== -1) { resArr[m - 1] = arr[indexArr[m - 1]] } else { //从m-2位开始 set(resArr, m - 1, indexArr, arr) } res = arrToNumber(resArr) } return res } getMin(arr, target)