在 JavaScript 中从已排序的文字数组中删除重复项
问题陈述说,用户给定一个已排序的数字数组作为输入源,因此我们需要从中删除重复或重复的元素,使其成为仅包含唯一元素的新数组。
什么是 JavaScript 中的已排序数组?
已排序数组是 JavaScript 中的一种数组,它遵循一定的行顺序,其中每个元素都按字母和数字顺序排序,然后再使用 JavaScript 本身中的排序方法。已排序的速度数组可让您加快搜索速度,并更轻松、更高效地对已排序数组执行其他操作。
问题陈述的输出是删除数字数组中存在的重复和冗余元素,可以直观地显示为:
const sortedArray = [ 1 , 2 , 2 , 3 , 4 , 6 ,6 ]; // 执行算法以删除重复项 const duplicateElementRemovedArray = [ 1 , 2 , 3 , 4 , 6 ];
算法
步骤 1:声明一个名为 removeDuplicates 的函数,该函数以问题陈述中提到的已排序数组作为输入源。
步骤 2:使用外部 for 循环从第 0 个索引遍历数组的每个元素到数组的长度。
步骤 3:使用内部循环,我们从已排序数组的长度(即最后一个元素)开始向后遍历,直到外部循环 i 值的一个索引增量。
步骤 4:现在使用比较运算符检查并比较外循环中 i 的一个值与每次迭代中 j 循环的每个值,以检查是否存在任何重复项。
步骤 5:如果发现任何重复项,则使用 splice 方法在相等匹配成功后删除 i 或 j 索引处重复值的特定元素,丢弃并删除重复元素,其中 splice 方法中的第二个参数表示要删除多少个字符。
步骤 6:使用嵌套循环完成所有重复项检查和删除后,成功返回唯一元素排序数组。
示例
function removeDuplicates(sortedArray) { for(let i = 0 ; i < sortedArray.length ; i++) { for( j = sortedArray.length ; j>=i+1 ; j--) { if(sortedArray[i] === sortedArray[j]) { sortedArray.splice(i,1); } } } return sortedArray; } const sortedArray = [ 1,1,2,3,4,4,5,6,6,7,8]; const uniqueElementsArray = removeDuplicates(sortedArray); console.log(uniqueElementsArray);
输出
[ 1, 2, 3, 4, 5, 6, 7, 8 ]
时间和空间复杂度
在上述算法中,我们最初使用了嵌套循环,该循环需要遍历 array.length,因此导致 O(n^2) 时间复杂度,而 JavaScript 的拼接方法也需要 O(n) 时间复杂度来提取或删除某些元素,因此导致 O(n^2) + O(n) = O(n^2) 最坏情况时间复杂度。
但空间复杂度是 O(1),即常数,因为我们没有分配任何额外的内存来完成从排序的数字数组中删除重复项的任务。稍后我们也可以使用该函数调用,控制台中的输出将是:
结论
这就是我们如何在编码上下文中逻辑思维地解决上述问题陈述,从嵌套循环遍历和访问数组元素,然后拼接 javascript 方法来完成问题陈述的执行。