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 = 4left=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)

这里在使用sort()函数时曾遇到了小bug：当添加状态的编号>10时，下次添加会是2. 原因

编号采用的是string类型js的sort函数默认是按照ACSII+字典序来排序的