在JavaScript数组中查找第一个重复项

作者 : IT 大叔 本文共1885个字,预计阅读时间需要5分钟 发布时间: 2020-10-15

在此博客文章中,我们将探讨作为软件工程师可能遇到的潜在面试问题的解决方案背后的思考过程:如何在数组中查找第一个重复元素(整数,字符串或其他)。

虽然这个问题可能比您在面试中会直接遇到的问题要简单一些,但我们将用来解决该问题的核心概念(以及提出该问题的过程)将在以后解决更复杂的问题上。

准备?我们走吧!


首先,让我们确保我们对想像的提示是清楚的:

给定包含整数,字符串或数据类型混合的数组,请在数组中找到第一个重复元素,其第二次出现具有最小索引。如果有多个重复的元素,则返回其第二次出现的索引比另一元素的第二次出现的索引小的元素。如果没有重复项,则返回“此处没有重复项!”。

当您看到这样的提示时,可能会与所有有关最小索引的说法有些混淆,但是当您将其归结为问题时,问题的实质实际上非常简单。本质上,要查询的是在数组中导航,并且第一次发现重复元素-这就是要返回的元素!用最小索引来描述它只是一种更技术上的表达方式,因为第一个重复项应该出现在数组中的较早/较低索引处

例如,让我们使用以下整数数组:

在JavaScript数组中查找第一个重复项插图

2、3和4在数组中都是重复的,但是3是在arr [4]的索引处列出的第一个重复项。那就是我们要通过函数返回的那个!


现在,让我们深入研究如何解决这个问题的思考过程。这是此问题的关键方面,甚至比解决方案本身更重要。

当我们看到这样的问题时,如果要在数组中查找涉及重复项的内容,无论是要找到它们,还是要消除它们,否则我们将很可能需要两件事:

  1. 遍历数组的循环
  2. 一种数据结构,其中包含要与之比较的循环的值。

这里的过程是:我们知道我们将需要查看给定数组的大多数(或可能是所有)元素-因此是for循环-并且我们将需要一些东西来保存每个这些被查看的值为了检查我们是否已经看过他们。这是一种逻辑方法,将在大量与数组有关的面试问题和算法中出现,因此感到非常有价值。

我们可以使用各种数据结构来保存这些值,但是如果我们牢记运行时的复杂性,则应在JavaScript的上下文中将其限制为哈希表MapSet对象。

我们在此处使用上述方法之一的原因是,我们将在每次循环中将给定数组的每个值与已看到的元素集进行比较-检查哈希表中的键或值与使用Array.includes()函数之类的东西相比,它是恒定的时间复杂度,该函数在每次通过时添加另一个嵌套迭代。在这种情况下,我们将使用Set对象,因为它可以完美地适应我们的特定情况。

是时候开始编写我们的解决方案了!


首先,让我们声明一下函数:

function firstDuplicate(arr) {

}

现在,让我们创建Set对象:

function firstDuplicate(arr) {
   let elementSet = new Set();
}

这个Set对象将允许我们将给定数组中的每个元素存储为唯一值,并使用以下两个函数检查它是否已经包含值:Set.add()Set.has()

现在,让我们通过给定数组实现循环:

function firstDuplicate(arr) {
    let elementSet = new Set();

    for (let i = 0; i < arr.length; i++) {

    } 
}

最后,我们将介绍算法的核心逻辑:

  1. 我们将检查Set是否已经包含我们当前在循环中使用的元素-如果存在,那么我们找到了第一个重复项!我们将返回该值并完成。
  2. 在达到该里程碑之前,我们需要有一个“ else”语句,以说明该元素是否尚未在Set中,在这种情况下,我们添加到Set中,然后移至数组中的下一个元素。
function firstDuplicate(arr) {
    let elementSet = new Set();

    for (let i = 0; i < arr.length; i++) {
        if (elementSet.has(arr[i])) return arr[i];
        elementSet.add(arr[i]);
    } 
}

只是最后一步:我们的优势案例,其中在阵列中找不到重复项!我们将在循环之后添加它,假设它已经完成而没有返回重复的值:

function firstDuplicate(arr) {
    let elementSet = new Set();

    for (let i = 0; i < arr.length; i++) {
        if (elementSet.has(arr[i])) return arr[i];
        elementSet.add(arr[i]);
    }

    return "No duplicates here!";
}

我们完成了!现在,我们已经掌握了快速检查并返回JavaScript数组中第一个重复项的知识,而与数据类型无关。此函数将返回整数数组,字符串数组或混合数组中的第一个重复项。

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 在JavaScript数组中查找第一个重复项

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论