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

🧡🧡遇到的问题🧡🧡

在用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)