JavaScript 从已排序文字数组中删除重复项
问题说明指出给定一个用户作为输入源的已排序数字数组,我们需要从中删除重复或重复的元素,使其成为包含仅唯一元素的全新数组。
JavaScript中的有序数组是什么
已排序数组是一种遵循特定顺序的JavaScript数组,其中每个元素在使用JavaScript本身的sort方法之前都按字母和数字顺序排序。已排序的速度数组可以加快搜索速度,并更轻松高效地执行其他操作。
问题说明的输出是删除数字数组中存在的重复和冗余元素,可以视为:
const sortedArray = [ 1 , 2 , 2 , 3 , 4 , 6 ,6 ];
// perform algorithm to remove duplicates
const duplicateElementRemovedArray = [ 1 , 2 , 3 , 4 , 6 ];
步骤
步骤1 : 声明一个名为removeDuplicates的函数,该函数接受一个按问题描述中所述的有序数组作为输入源。
步骤2 : 使用外部for循环从0索引到数组长度遍历数组的每个元素。
步骤3 : 使用内部循环,我们从排序数组的最后一个元素开始向后遍历,直到外部循环的i值加一为止。
步骤4 : 现在使用比较运算符来检查和比较外部循环中i的一个值与每次迭代中内部循环中j循环的每个值是否存在重复。
步骤5 : 如果找到任何重复项,splice方法被用来删除一个重复值的特定元素,即i或j索引上的元素,一旦相等匹配成功,删除重复元素的第二个参数告诉要删除的字符数量。
步骤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
]
时间和空间复杂度
在上述算法中,我们最初使用了嵌套循环,需要进行数组长度的遍历,因此导致时间复杂度为O(n^2),而JavaScript的splice方法提取或删除特定元素的时间复杂度也为O(n),因此最坏情况下的时间复杂度为O(n^2) + O(n) = O(n^2)。
但空间复杂度为O(1),即常量,因为我们没有分配任何额外的内存来完成从已排序的数组中删除重复元素的任务。之后,我们可以调用该函数并在控制台中输出结果:
结论
这就是我们如何在逻辑上和编码上解决上述问题陈述的方法,从嵌套循环遍历和访问数组元素,到使用splice JavaScript方法来完成问题陈述的执行。