JavaScript实现：查找指定范围乱序数字串中的可能缺失数字

需求说明 #

现有一个由连续整数区间[start, end]内数字生成的特殊字符串：

• 区间内所有数字直接拼接后打乱字符顺序，无法直接拆分识别单个数字
• 字符串恰好缺失区间内的某一个数字
• 函数需要返回所有符合字符计数规则的可能缺失数字组成的数组

示例：区间为1-21，输入字符串str = "2198765123416171890101112131415"，调用findNumber(1, 21, str)预期返回[12, 21]。因为从字符总量统计层面无法判定缺失的是12还是21，两个值都满足条件，需要全部返回。

实现思路 #

因为字符串是完全打乱的，不需要尝试拆分数字，只需要通过字符频次匹配判断即可：

• 首先统计输入字符串中0-9每个数字字符的出现次数
• 遍历区间内每一个数字，假设当前数字就是缺失值
• 统计区间内排除当前假设缺失值后，所有数字拼接得到的总字符频次
• 对比两组频次数据，如果完全一致，说明当前假设的缺失值是合法结果，加入返回数组

完整代码 #

function findNumber(start, end, str) {
  // 工具函数：统计字符串中各字符的出现频次
  const countChars = (target) => {
    const countMap = {};
    for (const char of String(target)) {
      countMap[char] = (countMap[char] || 0) + 1;
    }
    return countMap;
  };

  const inputCharMap = countChars(str);
  const possibleMissing = [];

  // 逐个验证每个数字作为缺失值的可能性
  for (let missingNum = start; missingNum <= end; missingNum++) {
    const currentMap = {};
    // 统计排除当前缺失值后，所有区间数字的总字符频次
    for (let num = start; num <= end; num++) {
      if (num === missingNum) continue;
      for (const char of String(num)) {
        currentMap[char] = (currentMap[char] || 0) + 1;
      }
    }
    // 校验两个频次表是否完全匹配
    let match = true;
    const allCheckKeys = new Set([
      ...Object.keys(inputCharMap),
      ...Object.keys(currentMap)
    ]);
    for (const key of allCheckKeys) {
      if ((inputCharMap[key] || 0) !== (currentMap[key] || 0)) {
        match = false;
        break;
      }
    }
    if (match) possibleMissing.push(missingNum);
  }

  return possibleMissing;
}

// 示例测试
const testStr = "2198765123416171890101112131415";
console.log(findNumber(1, 21, testStr)); // 输出 [12, 21]

内容的提问来源于stack exchange，提问作者Riaz Bappy