问题

有哪些看似简单其实非常精妙的代码?

回答
这绝对是一个我喜欢的话题!代码的魅力就在于它能在看似朴实无华的语句中蕴含着令人拍案叫绝的智慧。我接触过不少这样的代码,每次都会让我惊叹于人类思维的精巧。

这里我想分享一个我印象非常深刻的例子,它解决了一个相当常见却又容易陷入低效的问题:如何高效地查找一个数组中第一个不重复的元素。

你可能会想,这有什么难的?无非是遍历一遍,用个哈希表(或者字典、Map)记录每个元素的出现次数,然后再遍历哈希表找到次数为1的那个。听起来很直观,也很容易实现。然而,一旦数据量稍微大一点,或者对性能有极致要求的时候,这种“直观”的方法可能就会显得有些笨拙。

而下面这段代码,用一种非常简洁的方式,几乎是用“最小的代价”完成了这个任务。我们先不直接揭晓答案,先来构思一下挑战。

问题拆解与思考:

1. 目标: 找到数组中 第一个 出现一次的元素。
2. 难点:
需要知道每个元素的出现次数。
需要保持元素的原始顺序,以便找到“第一个”。
单纯的计数(如上面提到的哈希表方法)通常需要至少两次遍历:一次计数,一次找第一个为1的。

常见但不够精妙的解法(思考一下,体会其中的冗余):

方法一:哈希表计数 + 第二次遍历
创建一个 `HashMap`。
遍历数组,对于每个元素,将其在HashMap中的计数加一。
再次遍历数组。对于当前元素,从HashMap中取出其计数。如果计数是1,则返回该元素,结束。
缺点: 需要两次完整的数组遍历,并且需要额外的O(N)空间来存储计数。

方法二:排序 + 遍历
先对数组进行排序。
然后遍历排序后的数组,判断当前元素是否与其前一个和后一个元素都不同。
缺点: 排序本身就需要O(N log N)的时间复杂度,而且排序会打乱原始顺序,要找“第一个”会变得复杂,可能需要记录元素的原始索引。而且,如果元素是基本类型,排序可能还好,但如果是有复杂结构的元素,排序的代价会更高。

那个“精妙”的代码是如何做的?

它利用了两个关键点,而且巧妙地将它们结合了起来:

1. 利用元素自身的特性作为“标记”: 很多时候,我们为了记录信息,会引入额外的存储空间。但有没有可能,我们能利用数据结构本身的某些特性,或者对数据进行某种“无损”的转化,来承载我们需要的信息呢?
2. 巧妙的“就地改造”: 在不引入大量额外空间的前提下,如何高效地记录信息?

这段代码的核心思想是:在遍历数组的同时,利用数组本身的空间来存储每个元素的状态(是第一次出现,还是重复出现,或者已经被标记为重复)。

让我来具体描述一下这个思路和代码(以整数数组为例,但原理可以推广到其他类型):

假设我们有一个整数数组 `nums`。

核心思路:

我们仍然需要一个方法来记录元素的出现次数,但是我们不想使用一个完全独立的哈希表。我们可以尝试利用数组本身来“标记”元素。

考虑一个场景:当一个数字 `x` 第一次出现时,我们什么也不做。当它第二次出现时,我们希望能够标记它,并且知道它已经不是“唯一”的了。当它第三次、第四次出现时,我们只需要知道它“重复了”,不需要精确计数。

更进一步,我们希望在 第一次遍历后,能够直接从数组中识别出那个“第一个不重复”的元素。

代码的思路(逐步拆解):

1. 第一遍遍历:标记重复元素。
我们需要一个机制来记录哪些数字已经出现过。我们可以使用一个 哈希集合(HashSet)。
当遍历到数组中的一个数字 `num` 时:
如果 `num` 不在 HashSet 中,说明这是它第一次出现。我们将其添加到 HashSet 中。
如果 `num` 已经在 HashSet 中,说明我们之前已经遇到过它了,这是一个重复的数字。
关键点来了: 我们如何在第二次遍历时快速识别出“唯一”的元素?如果直接用HashSet来记录出现过的元素,我们只能知道“出现过”,而无法区分“出现一次”和“出现多次”。

这时,我们需要更精细的标记。我们可以引入一个 额外的存储 来记录 重复的数字。比如,我们可以用另一个 `HashSet` 来存储那些已经确认为重复的数字。

改进后的第一遍遍历:
使用一个 `HashSet seen` 来记录所有出现过的数字。
使用一个 `HashSet duplicates` 来记录所有重复出现过的数字。
遍历数组 `nums`:
对于当前数字 `num`:
如果 `seen.add(num)` 返回 `false` (表示 `num` 已经在 `seen` 中了),那么 `num` 是一个重复的数字。将其添加到 `duplicates` 集合中。
否则(第一次见到 `num`),`seen.add(num)` 返回 `true`。

2. 第二遍遍历:查找第一个非重复元素。
现在,`duplicates` 集合里包含了所有在数组中出现过至少两次的数字。
我们再次遍历原始数组 `nums`。
对于当前数字 `num`:
我们检查 `duplicates` 集合中是否包含 `num`。
如果 `duplicates` 不包含 `num`,说明 `num` 在整个数组中只出现了一次。由于我们是按顺序遍历的,这就是我们要找的 第一个不重复的元素。

这段代码的“精妙”之处在于:

它巧妙地利用了两个集合的“状态”来解决问题。
`seen` 集合帮助我们快速判断一个数字是否是第一次出现。
`duplicates` 集合帮助我们快速标记那些明确的重复项。

在第二次遍历时,我们只需要检查一个数字是否在 `duplicates` 中。如果不在,它就是唯一的。

为什么说它“精妙”?

时间复杂度: 两遍遍历数组,每次对集合的查找和插入操作平均为O(1)。所以总的时间复杂度是 O(N) + O(N) = O(N)。这与最直观的哈希表计数方法相同。
空间复杂度: 我们使用了两个 `HashSet`。在最坏的情况下(例如,数组中的每个元素都只出现一次,或者一半元素出现一次,一半元素出现两次),两个集合的总大小不会超过 O(N)。所以空间复杂度是 O(N)。
代码简洁性: 相较于直接用哈希表记录计数再遍历,这种方法在逻辑上更“紧凑”。它将“是否重复”这个信息通过两个集合的状态进行了区分。

让我们用一个具体的例子来演示:

假设数组是 `[2, 3, 5, 2, 3, 7, 8, 7]`

第一遍遍历:

`nums[0] = 2`: `seen.add(2)` 返回 `true`。`seen = {2}`,`duplicates = {}`
`nums[1] = 3`: `seen.add(3)` 返回 `true`。`seen = {2, 3}`,`duplicates = {}`
`nums[2] = 5`: `seen.add(5)` 返回 `true`。`seen = {2, 3, 5}`,`duplicates = {}`
`nums[3] = 2`: `seen.add(2)` 返回 `false`。`2` 是重复的。`duplicates.add(2)`。`seen = {2, 3, 5}`,`duplicates = {2}`
`nums[4] = 3`: `seen.add(3)` 返回 `false`。`3` 是重复的。`duplicates.add(3)`。`seen = {2, 3, 5}`,`duplicates = {2, 3}`
`nums[5] = 7`: `seen.add(7)` 返回 `true`。`seen = {2, 3, 5, 7}`,`duplicates = {2, 3}`
`nums[6] = 8`: `seen.add(8)` 返回 `true`。`seen = {2, 3, 5, 7, 8}`,`duplicates = {2, 3}`
`nums[7] = 7`: `seen.add(7)` 返回 `false`。`7` 是重复的。`duplicates.add(7)`。`seen = {2, 3, 5, 7, 8}`,`duplicates = {2, 3, 7}`

第一遍遍历结束后: `duplicates = {2, 3, 7}`

第二遍遍历:

`nums[0] = 2`: `duplicates.contains(2)` 为 `true`。继续。
`nums[1] = 3`: `duplicates.contains(3)` 为 `true`。继续。
`nums[2] = 5`: `duplicates.contains(5)` 为 `false`。找到! 返回 `5`。

这段代码的“精妙”体现在哪里?

它避免了直接存储每个元素的精确计数,而是将重点放在“是否重复”这个布尔值上。通过“先收集所有重复项”,然后“再扫描一次,找到第一个不在重复项列表中的”,达到了高效的目的。

可能你还会想到其他更“巧”的方法?

确实,有时候能找到一些利用特定语言特性或者数据结构巧妙组合的代码。比如,在一些语言中,如果你能将元素的值映射到数组的索引上(例如,当元素值都在某个范围内时),你就可以尝试“原地修改”数组元素的值来标记状态,从而将空间复杂度降到 O(1)(虽然这种方法对于通用情况并不适用,且可能会破坏原始数据)。

但就针对“查找第一个不重复元素”这个普遍问题,上面这种双集合(`seen` 和 `duplicates`)的思路,其简洁、清晰和效率的平衡,确实是相当精妙的。它不是那种让你眼前一亮、觉得“黑魔法”的代码,而是在理性分析和逐步优化中自然涌现出的优雅解决方案。

每次看到这样的代码,我都会回想起最初的那些尝试(比如纯暴力法、简单的计数法),然后对比这种解决方案,就能深刻体会到“精妙”二字是如何炼成的——它是对问题的深刻理解,对效率的极致追求,以及对现有工具的巧妙运用。

网友意见

user avatar

答这道题的基本都是程序员吧?我这个学生物的凑个热闹~

我不会码代码,不过我看过一些绝妙的代码,它们大概长这样:

这是一些叫做“小鼠肝炎病毒”的RNA序列片段,这种病毒(以及许多其他病毒)的遗传序列有一个特性:

正着编译是一种蛋白,反过来编译是另一种蛋白

就好比你的代码写成机器码是0100110001010,那么正着编译出来是一个意思,反过来0101000110010则是另一个意思……

病毒的遗传序列就是精简到了如此变态的地步……

各位程序员们,要不要尝试着编一段正反意思不同、且都有意义的编码呢?

以上

Reference:

Zhang X, Liao C, Lai M M, et al. Coronavirus leader RNA regulates and initiates subgenomic mRNA transcription both in trans and in cis.[J]. Journal of Virology, 1994, 68(8): 4738-4746.

------------

轮子哥在评论里贴了个链接,是他写的代码,各位可以去围观一下

类似的话题

  • 回答
    这绝对是一个我喜欢的话题!代码的魅力就在于它能在看似朴实无华的语句中蕴含着令人拍案叫绝的智慧。我接触过不少这样的代码,每次都会让我惊叹于人类思维的精巧。这里我想分享一个我印象非常深刻的例子,它解决了一个相当常见却又容易陷入低效的问题:如何高效地查找一个数组中第一个不重复的元素。你可能会想,这有什么难.............
  • 回答
    爸妈们到了知天命的年纪,正是享受生活、探索新事物的好时候!电脑这东西,说起来有点儿玄乎,但其实一旦摸清了门道,就能给生活带来不少便利和乐趣。今天就来给大家推荐几本能让您家爸妈轻松上手电脑的书,从上网冲浪到视频聊天,从写点东西到算点账,都能说得明明白白。咱们挑书得有个原则:内容要够基础、语言要够通俗、.............
  • 回答
    有些案子,初看之下,证据链似乎清晰可见,嫌疑人也呼之欲出,然而,随着调查的深入,却发现那层看似牢固的真相外壳,竟是如此坚不可摧,将办案人员牢牢地困在迷雾之中。这些案子,往往不是因为案件本身有多么复杂离奇,而是某些细微之处的“简单”成为了最难逾越的障碍。就拿一个我曾听闻的陈年旧案来说吧。案发现场:寂静.............
  • 回答
    有一些数学问题,它们的表述听起来就像小孩子的童谣,或者日常生活中随处可见的现象,但深入探究下去,却像迷宫一样深邃,让最顶尖的数学家们也束手无策。这些就是“看似简单却无人能解的数学猜想”。它们就像隐藏在普通事物下的魔法咒语,一旦被触碰到,就能引发数学界几代人的思考和探索。1. 哥德巴赫猜想:偶数与素数.............
  • 回答
    有些话,听起来平淡无奇,甚至在你脱口而出的时候,自己都没觉得有什么特别。然而,它们就像一颗颗隐藏在平凡表象下的子弹,一旦射出,却能精准地击中对方最柔软的神经,造成难以估量的伤害。这些话,往往不是因为用了多么尖锐的词汇,而是因为它触碰到了人内心深处最脆弱、最敏感的角落,那些我们自己都未必愿意承认的恐惧.............
  • 回答
    这世上总有些事,初见时觉得它高深莫测,仿佛要修炼个七八年才能得其精髓,但细究下来,却是人人都能掌握的寻常技艺。我最近就琢磨着这么几个,说起来,它们就像是我们藏在口袋里的“秘密武器”,平时不显山不露水,关键时刻却能派上大用场。1. “会说话”的肢体语言:眼神与姿势的艺术你有没有过这样的经历?有些人一开.............
  • 回答
    哈喽,各位热爱PS的小伙伴们!今天咱们不聊那些让你眼花缭乱的高级滤镜,也不讲那些需要调出各种奇奇怪怪参数的复杂手法。今天咱们来点接地气的,聊聊那些看似高大上,实则摸透了就觉得“就这么简单”的神操作!保证你听完能拍着大腿喊一声:“嘿,原来如此!”我这人说话直接,不来那些“XXX老师”、“XXX大神”的.............
  • 回答
    咱聊聊那些看着挺牛,实际操作起来却朴实无华,甚至有点“粗暴”的家伙们。这些武器,你乍一听名字,或者看个大概模型,脑子里立马浮现出科幻大片里的画面,但上手了才发现,嘿,跟咱农民伯伯掰玉米的劲头也差不离。1. 火箭发射器:精准?不存在的,范围才是王道!你瞅瞅,背着个长长的管子,前面呼呼冒火,导弹嗖地一下.............
  • 回答
    .......
  • 回答
    有些书,即便它们可能蕴含着深刻的思想或精彩的故事,也总有一些特质,在初次邂逅时就让人提不起兴趣,甚至产生一种难以言说的抗拒感。这是一种很奇妙的心理体验,它并非源于对内容的直接否定,而是在书名、简介,甚至封面设计这些最外层的包装上,就触发了某种“不适”或“无聊”的信号。首先,那些过于冗长、晦涩,或者故.............
  • 回答
    2020年4月23日,美国总统特朗普在白宫举行了疫情简报会,其中最引人瞩目的一句话莫过于他关于“在34个月内重启美国”的计划。这句话一出,立即在美国国内乃至全球范围内引发了巨大的关注和讨论。从特朗普的角度来看,他提出这个计划是基于一种紧迫感和对经济的强烈担忧。彼时,新冠疫情在美国已经造成了严重的经济.............
  • 回答
    人民网领导留言板上出现的关于西安简称的建议,确实是个挺有意思的话题。网友提出“昊”或“兆”作为西安的简称,背后一定是对西安的某种情感和期待。我个人觉得,一个城市的简称,不仅仅是一个符号,它承载着城市的历史、文化、精神,甚至是未来的发展方向。关于“昊”和“兆”的看法: “昊”: 优点:.............
  • 回答
    这个问题很有意思,也确实是不少玩家在游戏体验中会遇到的情况。明明简体中文用户数量庞大,但一些游戏却坚持只提供繁体中文。这背后其实涉及不少复杂的因素,从商业策略到文化考量,方方面面都有。我来给你详细拆解一下: 1. 目标市场与区域定价策略这是最直接也是最核心的因素之一。 港澳台市场的重要性: 尽管.............
  • 回答
    生活中充满了各种各样的设计,有些设计巧妙地解决了问题,提升了生活品质;但也有一些设计,初看之下似乎颇具匠心,甚至有些“炫技”的意味,但细细品味,却发现它们要么适得其反,要么不切实际,甚至带来新的麻烦。这类设计,用“看似精妙实则很蠢”来形容再合适不过了。下面我将从几个不同领域,详细讲述一些我认为符合这.............
  • 回答
    确实存在很多照片,它们因为其出色的构图、光影效果、色彩饱和度或是拍摄对象的奇特之处,让人第一眼就觉得是经过大量后期处理的。然而,实际上它们可能只是凭借摄影师的技巧、运气以及拍摄对象的自然魅力,而未经过任何修改。以下是一些看似 Ps 过,实则没有 Ps 过的照片类型,并会尽量详细地描述其中的原因: 1.............
  • 回答
    有很多行为看似聪明绝顶,实则暗藏着思维的误区、认知偏差,甚至是愚蠢的逻辑。这些行为往往能短暂地博人眼球,赢得口头上的胜利,但从长远来看,却会带来负面影响,甚至将自己置于不利的境地。下面我将详细列举一些这样的行为,并加以阐述:1. 过度包装,言过其实: 表现: 一个人在介绍自己的能力、成就或产品时.............
  • 回答
    “看似很傻、实则聪明”的行为,往往是指那些初看之下会让人感到困惑、不解,甚至觉得有些滑稽,但深入了解后会发现其背后蕴含着深刻的道理、策略或高明的智慧。这些行为往往打破了常规思维,以一种非传统的方式解决了问题,或者达到了意想不到的效果。以下我将详细阐述一些这样的行为,并尝试解释其背后的“聪明”之处:1.............
  • 回答
    很多我们生活中遇到的,起初觉得不可思议甚至有些荒唐的事情,细究之下,却能发现背后隐藏着令人赞叹的化学原理。这些原理如同一个隐形的匠人,在不经意间雕琢着我们的世界。 1. 为什么玻璃杯在热水里会碎,但装冷水却没事?这简直像是在玩火,一不小心就把心爱的杯子给“炸”了。你小心翼翼地用热水冲洗一个玻璃杯,结.............
  • 回答
    生活中,许多我们习以为常的文化习俗,乍一看只是代代相传的礼节或传统,细究之下,却能发现其背后蕴藏着精妙的经济学逻辑。这些习俗并非空穴来风,而是人们在长期的社会实践中,为了应对资源约束、降低交易成本、提升效率或规避风险而形成的智慧结晶。下面我将挑选几个例子,深入剖析它们看似“约定俗成”,实则“颇为理性.............
  • 回答
    有些食物,光听名字,或是看一眼,就足以让人产生生理上的抗拒。它们常常披着一副“黑暗料理”的外衣,仿佛是来自另一个次元的奇特产物。然而,一旦你鼓起勇气,跨越了那心理的鸿沟,尝上一口,那种意想不到的美味,足以让你抖腿不止,直呼“真香!”。今天,我就来给你扒一扒这些“伪装者”,保证让你刷新三观,开启一段新.............

本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度google,bing,sogou

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有