当前位置：首页 > article >正文

vue3项目实践心得-寻找未被使用的最小编号

article 2025/2/25 15:07:49

🧡🧡遇到的问题🧡🧡

在用vue3+ts编写编译原理项目中”绘制状态转换图“时，有一个添加状态的功能按钮，用户点击按钮即可添加一个新的状态，至于新的状态的编号值，想着以”最小未被使用的编号“为准则，即

若已存在0，1，2，3等编号，则新添加的编号应为4
若已存在0，1，3，4等编号，则新添加的编号应为2

🧡🧡主要思路🧡🧡

1.很直接很简单思路，直接暴力枚举

  // 暴力法找到最小的未被使用的编号
  let newNumber = 0;
  for (let i = 0; i < usedNumbers.length; i++) {
    if (usedNumbers[i] !== i) {
      newNumber = i;
      break;
    }
    newNumber = i + 1; // 如果所有编号都被使用，则使用下一个编号
  }
  console.log(usedNumbers)

2.后面经过思索，发现是一个有序序列，好在之前学习过二分算法，很快就联想到了

  // 二分查找最小的未被使用的编号
  let left = 0;
  let right = usedNumbers.length;
  while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (usedNumbers[mid] === mid) { // 说明 0 到 mid 都被使用
          left = mid + 1;
      } else {
          right = mid;
      }
  }
  const newNumber = left;

解释：

给定0，1，2，3，5，6，7
初始 left = 0， right=7 （注意这里left、right、mid都表示的数组下标，而非数组值）
第一轮 mid=3，从而有 useNumbers[3[ == 3，表明从left=0到mid=3是连续的，因此”最小未被使用“编号肯定不是这left=0到mid=3的区间，因此重置下一轮left = mid + 1 = 3 + 1 = 4
left=4， right=7
第二轮 mid=5，从而有 useNumbers[5] = 6 !== 5，表明数组下标从left=4到mid=5是不连续的，因此”最小未被使用“编号可能存在于这区间之中，因此重置下一轮right = mid = 5
以此类推。。。

🧡🧡其他细节🧡🧡

因为编号是用户可以手动修改的，可能会有编号为空或者编号含非数字字符等情况，因此需要在获取当前已使用的编号时，去除掉其中非数字编号。
在这里插入图片描述

  // 提取所有已使用的编号
  // 过滤非数字 + 去重 + 排序
  const usedNumbers = Array.from(new Set(getNodes.value
    .map(node => {
          const num = Number(node.data.text)
          // console.log(num)
          return isNaN(num)? null : num
      })
    .filter((num): num is number => num!== null))) // 显式断言num is number
    .sort((a,b)=> a-b)