专栏首页五分钟学算法(美团)巧用数组下标,轻轻松松找出所有元素

(美团)巧用数组下标,轻轻松松找出所有元素

大家好,我是吴师兄。

今天分享的算法题和 数组 这个数据结构有关,如果你不了解数组的特点,你百分百无法想到它的解法。

题目描述

给定一个整数数组 a,其中 1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次

找到所有出现两次的元素。

你可以不用到任何额外空间并在 O(n) 时间复杂度内解决这个问题吗?

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]

来源:https://leetcode-cn.com/problems/find-all-duplicates-in-an-array

题目解析

输入数组包含值为 1 ~ n(n 是数组的长度)的元素。这里面有的元素出现了两次,有的元素出现了一次,找出那些出现两次的元素。最后,题目还加了实现上的限制条件,那就是不能使用额外的空间,而且时间必须在 O(n) 内。

首先还是考虑常规的解法,也就是没有时空上面的限制条件的话,你会如何来解题?

如果没有空间上面的限制,那么我们完全可以使用哈希表来进行操作,也就是先用哈希表统计每个元素出现的个数,然后遍历一遍哈希表找出那些出现两次的元素即可,这么下来时间上也是满足条件的,但就是用到了额外的空间。

还有一种思路是排序,排序后,相同的元素会紧挨在一起。在遍历一遍数组,根据元素的相邻元素来找出那些出现两次的元素。这么下来虽说没有用到额外的空间,但是因为有排序,时间并不在 O(n) 内。

上面的那两种思路都是常规的思路,一般有一点编程经验的人都能想得到。

那要如何做才能既满足空间又满足时间呢?

因为题目给的信息并不复杂,就是一个整形数组,那么我们就要借助整形数组本身来解题。

数组本身其实就两个信息,一个是下标,另一个是元素的值。那么我们就需要构建下标和元素的值的联系

你可能会说,下标和元素的关系不是很直白吗?我们通过下标可以直接找到元素,下标就是元素的索引。对,没错,但是不知道你有没有发现数组里的元素的值的范围是在 [0, n] 之间的。

这也就为反向从元素值本身出发定位到下标提供了可能,如果有两个元素都定位到了同一个下标,那说明什么?

说明了这个元素出现过两次,我们就需要记录下来。

剩下的问题就是,“如何记录次数呢?”。

因为数组里的元素要么出现了一次,要么出现了两次,其实不用记录完整的次数。每当遍历到一个元素,我们只需要标记一下这个元素对应的下标出现过即可,那么下一次另外一个元素定位到同样的下标就可以确定之前有遍历到相同的元素。

那怎么标记才不会使元素失去其原本的意义呢?答案是直接取反

参考代码

func findDuplicates(nums []int) []int {
    if len(nums) == 0 {
        return []int{}
    }

    results := []int{}

    for i := 0; i < len(nums); i++ {
        // 获得元素 “匹配” 的下标
        // 因为有可能被取反过,所以这里取个绝对值
        index := abs(nums[i]) - 1

        // 当元素对应的下标的元素被取反
        // 说明该元素之前出现过,需要记录
        if nums[index] < 0 {
            results = append(results, index + 1)
        }

        // 标记,取反
        nums[index] = -nums[index]
    }

    return results;
}

func abs(a int) int {
    if a < 0 {
        return -a
    }

    return a
}

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:P.yh

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从简单的线性数据结构开始:栈与队列

    在计算机领域离不开算法和数据结构,而在数据结构中尤为重要与基础的便是两个线性数据结构:栈与队列,本文将简单的介绍栈(Stack)和队列(Queue)的实现。

    五分钟学算法
  • LeetCode 图解 | 27.移除元素

    给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

    五分钟学算法
  • 如何高效对有序数组/链表去重?

    我们知道对于数组来说,在尾部插入、删除元素是比较高效的,时间复杂度是 O(1),但是如果在中间或者开头插入、删除元素,就会涉及数据的搬移,时间复杂度为 O(N)...

    五分钟学算法
  • python笔记

    在python中列表用[]来表示,逗号分隔元素, 例如cars = [1,2,3]

    blankmiss
  • [OHIF-Viewers]医疗数字阅片-医学影像-querySelector() 选择器语法-将画布(canvas)图像保存成本地图片的方法

    使用HTML5画布技术,你可以在浏览器客户端用JavaScript绘制出各种美丽酷炫的图案,这些图案是不能直接保存的,本身也不是图片形式。

    landv
  • 再谈Heap(堆)的妙用

    好久没更新了,今天我又来了。一直看我文章的朋友可能会发现,我之前多次提到堆这个数据结构,它可以帮助我们快速地在一堆数据中,找到符合某个条件的最大或者最小的元素。...

    写代码的阿宗
  • 数组和链表的区别

    数组: 数组是将元素在内存中连续存放,由于每个元素占用内存 相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内...

    猿人谷
  • Pseudo elements伪元素与Pseudo classes伪类

    ::after用于描述处于css渲染层的一个伪元素,相当于选中元素的最后一个子元素,但这个元素与DOM节点无关,位于选择的元素之后,伪元素的内容用content...

    gojam
  • 我不知道你知不知道我知道的伪元素小技巧

    伪元素能做什么?我们要他有何用?它能为我们解决什么问题?和其他的方法相比她有什么有点?我们为什么要使用它?

    sunseekers
  • JavaWeb(八)JQuery

    jQuery 市场用得比较多两个框架: jQuery 比较适合做一些互联网 的应用(12306.com,蘑菇街,美丽说,聚美) extjs 比较适合做后台管理系...

    二十三年蝉

扫码关注云+社区

领取腾讯云代金券